Katkat
Back

Find the Lowest Common Ancestor in a Binary Search Tree

MicrosoftMachine Learning Engineer · HR Screen
MediumMachine Learning EngineerHR ScreenCoding & Algorithms

Last updated

This problem tests the ability to leverage the Binary Search Tree (BST) property to efficiently locate the Lowest Common Ancestor (LCA) of two nodes.

Problem: Find the Lowest Common Ancestor in a BST

Given a root of a Binary Search Tree (BST) and two values p and q, find the lowest common ancestor (LCA) of these two nodes in the BST.

The LCA of two nodes p and q is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root: 'TreeNode', p: int, q: int) -> 'TreeNode':

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9.
  • All Node.val are unique.
  • p and q will exist in the BST.

Examples

Example 1: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of 2 and 8 is 6.

Example 2: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of 2 and 4 is 2, since a node can be a descendant of itself.

Edge Cases

  • The LCA could be the root itself.
  • One of the target values could be a direct ancestor of the other.

Hints

Hint 1

Consider the BST property: for any node, all nodes in the left subtree have values smaller than the node, and all nodes in the right subtree have values larger.

Hint 2

If both p and q are smaller than the current node, the LCA must be in the left subtree; if both are larger, it must be in the right subtree.

Hint 3

If p and q are on opposite sides of the current node, or if the current node equals either p or q, then the current node is the LCA.

Follow-up questions

  • How would your approach change if the tree was a regular Binary Tree instead of a BST?
  • Can you implement this iteratively to achieve O(1) auxiliary space complexity?
  • What is the time complexity of your solution in terms of the height of the tree versus the total number of nodes?