Scale Engineer

Lowest Common Ancestor of a Binary Search Tree

Med
#0223Time: O(N) where N is the number of nodes in the tree as we might need to visit all nodesSpace: O(H) where H is the height of the tree due to recursive call stack6 companies
Algorithms
Depth-First Search
Data structures
TreeBinary TreeBinary Search Tree
Companies
GoogleLinkedInOracleSamsung

Prompt

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

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 nodes 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 nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a recursive depth-first search to traverse the binary search tree and find the lowest common ancestor. It doesn't utilize the BST property and treats it as a regular binary tree.

Algorithm

  1. If root is null or equals either p or q, return root
  2. Recursively search in left subtree
  3. Recursively search in right subtree
  4. If both left and right searches return non-null values, current node is LCA
  5. Otherwise, return the non-null value from either left or right

Walkthrough

The recursive approach works by traversing the tree and checking if the current node is either p or q. If we find either p or q, we return that node. If we get non-null values from both left and right subtrees, the current node is the LCA. If we get a non-null value from only one side, we propagate that up.

class Solution {    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        // Base case: if root is null or equals either p or q        if (root == null || root == p || root == q) {            return root;        }                // Recursively search in left and right subtrees        TreeNode left = lowestCommonAncestor(root.left, p, q);        TreeNode right = lowestCommonAncestor(root.right, p, q);                // If both left and right are non-null, root is the LCA        if (left != null && right != null) {            return root;        }                // Return non-null value        return left != null ? left : right;    }}

Complexity

Time

O(N) where N is the number of nodes in the tree as we might need to visit all nodes

Space

O(H) where H is the height of the tree due to recursive call stack

Trade-offs

Pros

  • Works for any binary tree, not just BST

  • Simple to understand and implement

  • Can be extended to find LCA of more than two nodes

Cons

  • Doesn't utilize BST properties

  • Uses more space due to recursive calls

  • Visits unnecessary nodes

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode LowestCommonAncestor ( TreeNode root , TreeNode p , TreeNode q ) { while ( true ) { if ( root . val < Math . Min ( p . val , q . val )) { root = root . right ; } else if ( root . val > Math . Max ( p . val , q . val )) { root = root . left ; } else { return root ; } } } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem