Find LCA of two nodes in BST

Problem Overview

The problem "Lowest Common Ancestor of a Binary Search Tree" involves finding the lowest common ancestor (LCA) of two nodes in a binary search tree (BST). The LCA is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants. A binary search tree is a special type of binary tree where each node has a comparable key (and an associated value) and satisfies the restriction: the key in each node is larger than the keys in the node's left subtree and smaller than the keys in its right subtree.

Understanding the Problem

To understand this problem, consider the properties of a BST that help us efficiently find the LCA. Given the value constraints of BST nodes, the path to any node in the tree can be unambiguously determined by comparing node values. This property can be utilized to trace back paths for two nodes and find their earliest intersection point, which is the LCA.

Example

Suppose we have the following BST:

       6
      / \
     2   8
    / \ / \
   0  4 7  9
     / \
    3   5

For nodes 2 and 8, the LCA is 6, and for nodes 2 and 4, the LCA is 2 itself.

Key DSA Concepts and Theory

Binary Search Tree (BST)

• Structure: A BST is a binary tree where each node has a key greater than all the keys in its left subtree and less than all the keys in its right subtree.
• Search Efficiency: Due to its sorted nature, a BST allows for efficient searching, insertion, and deletion operations, typically taking O(log n) time on average.

Lowest Common Ancestor (LCA)

• Definition: The lowest common ancestor between two nodes p and q in a binary tree is the lowest (i.e., deepest) node that has both p and q as descendants.
• Properties in BST: In a BST, the LCA of two nodes p and q is the first node traversed from the root that lies between the values of p and q.

Solution Approach

We leverage the properties of BSTs to identify the LCA efficiently. The algorithm can be stated as follows:

1. Initialize: Start at the root of the BST.
2. Traverse:
   • If both p and q are smaller than the current node, move to the left child.
   • If both are larger, move to the right child.
   • If one is smaller and one is larger, the current node is the LCA.
3. Return: When you identify the LCA, return it.

Let's demonstrate this with code implementations.

C++ Code Implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root != nullptr) {
            if (p->val < root->val && q->val < root->val) {
                root = root->left;
            } else if (p->val > root->val && q->val > root->val) {
                root = root->right;
            } else {
                // This is the split point, i.e., the LCA node.
                return root;
            }
        }
        return nullptr; // just a safety return, code should never reach here.
    }
};

Java Code Implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                // This is the split point, i.e., the LCA node.
                return root;
            }
        }
        return null; // just a safety return, code should never reach here.
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(h), where h is the height of the BST. This is because in each step, the algorithm discards half of the remaining subtree (binary partitioning), traversing down the height of the tree.
• Space Complexity: O(1) for the iterative approach because no additional space is used that scales with input size.

Common Mistakes to Avoid

• Misunderstanding BST Properties: Ensure that comparisons are correctly made based on node values to decide the direction of traversal.
• Incorrect Base Case: Failing to handle the scenario where p or q could be the LCA itself. The algorithm inherently covers this case through its checks.

Similar Problems on LeetCode

• 236. Lowest Common Ancestor of a Binary Tree
• 450. Delete Node in a BST
• 235. Lowest Common Ancestor of a BST

Additional Resources and References

• Binary Search Tree on GeeksforGeeks
• Lowest Common Ancestor explanation on YouTube

This article has explored the LCA problem for a BST, highlighting how understanding the properties of BSTs leads to an efficient linear-time algorithm. By observing how node values dictate movement, one can reliably determine the LCA in a single traversal from the root of the tree.