How do you solve Lowest Common Ancestor of a Binary Search Tree on LeetCode?

Lowest Common Ancestor of a Binary Search Tree (LeetCode #235) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The properties of BSTs allow for efficient searching and ancestor finding.

What is the time complexity of Lowest Common Ancestor of a Binary Search Tree?

The optimal solution for Lowest Common Ancestor of a Binary Search Tree runs in O(n) time and uses O(1) space. This complexity is linear because, in the worst case, we might traverse the height of the tree, which is O(n) for a skewed tree, but O(log n) for a balanced tree.

What is the brute force solution for Lowest Common Ancestor of a Binary Search Tree?

The brute force approach for Lowest Common Ancestor of a Binary Search Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking every node in the tree to see if it is the ancestor of both nodes p and q. This is straightforward but inefficient, as it requires traversing the entire tree. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Lowest Common Ancestor of a Binary Search Tree?

Always consider the properties of the data structure you're working with. Think about edge cases, such as when one node is the ancestor of the other. Practice explaining your thought process as you code.

What are common mistakes when solving Lowest Common Ancestor of a Binary Search Tree?

Not leveraging the properties of the BST, leading to inefficient solutions. Confusing the definition of LCA with other tree properties.

#235

Lowest Common Ancestor of a Binary Search Tree

Medium

TreeDepth-First SearchBinary Search TreeBinary TreeBinary SearchDepth-First Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

In a binary search tree, the properties of the tree allow us to find the LCA efficiently. We can leverage the fact that all nodes to the left are smaller and all nodes to the right are larger than the root.

⚙️

Algorithm

4 steps

1Step 1: Start from the root of the BST.
2Step 2: If both p and q are smaller than the current node, move to the left child.
3Step 3: If both p and q are larger than the current node, move to the right child.
4Step 4: If one of p or q is on one side and the other is on the other side, the current node is the LCA.

solution.py15 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def lowestCommonAncestor(root, p, q):
9    while root:
10        if p.val < root.val and q.val < root.val:
11            root = root.left
12        elif p.val > root.val and q.val > root.val:
13            root = root.right
14        else:
15            return root

ℹ

Complexity note: This complexity is linear because, in the worst case, we might traverse the height of the tree, which is O(n) for a skewed tree, but O(log n) for a balanced tree.

1The properties of BSTs allow for efficient searching and ancestor finding.
2The LCA can be found without storing all ancestors, saving space.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.