{x}
blog image

Lowest Common Ancestor of a Binary Search Tree

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.

Solution Explanation: Lowest Common Ancestor of a Binary Search Tree

This problem asks to find the Lowest Common Ancestor (LCA) of two nodes (p and q) in a Binary Search Tree (BST). The LCA is the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).

There are two main approaches to solve this problem efficiently: iterative and recursive. Both leverage the property of a BST:

  • Left Subtree: All nodes in the left subtree of a node are smaller than the node's value.
  • Right Subtree: All nodes in the right subtree of a node are greater than the node's value.

Approach 1: Iterative Solution

This approach uses a while loop to traverse the tree. We start at the root. At each node:

  1. If both p and q are smaller: The LCA must be in the left subtree. Move to the left child (root = root.left).
  2. If both p and q are larger: The LCA must be in the right subtree. Move to the right child (root = root.right).
  3. Otherwise: The current node (root) is the LCA because one node is smaller and the other is larger than the current node's value. Return the current node.

Time Complexity: O(h), where h is the height of the BST. In the worst case (a skewed tree), h could be equal to n (number of nodes). In a balanced BST, h is log n. Space Complexity: O(1). The iterative approach uses constant extra space.

Approach 2: Recursive Solution

This approach uses recursion. The logic is similar to the iterative approach:

  1. Base Case: If the current node's value is between p and q (inclusive), the current node is the LCA.
  2. Recursive Step: If both p and q are smaller than the current node's value, recursively search the left subtree. If both are larger, recursively search the right subtree.

Time Complexity: O(h), where h is the height of the BST. Similar to the iterative approach, it's O(n) in the worst case and O(log n) in a balanced BST. Space Complexity: O(h), where h is the height of the BST. This is due to the recursive call stack. In the worst case (skewed tree), it's O(n), and in a balanced BST, it's O(log n).

Code Examples (Python, Java, C++, Go, TypeScript)

The code examples provided earlier demonstrate both approaches. The iterative solution is generally preferred for its slightly better space complexity, especially in cases of very deep trees. However, the recursive solution might be considered more readable for some. The choice depends on the specific context and priorities (readability vs. space optimization).