algoadvance

Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) 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).”

The function signature will be:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)

Clarifying Questions

1. Input Validation: Can we assume that p and q are always present in the given BST?
   • Yes, you can assume that both p and q exist in the BST.
2. Tree Structure: Is it possible that the tree could be just one node, which means root, p, and q are the same?
   • Yes, that is possible.
3. Tree Node Values: Can the values of the tree nodes be any integer value?
   • Yes, the values of the tree nodes can be any integer.

Strategy

Given that this is a Binary Search Tree (BST), we can leverage the properties of BST for an efficient solution:

1. BST Property: For any node n, all nodes in the left subtree of n have smaller values, and all nodes in the right subtree have larger values.
2. Traverse the Tree:
   • Start at the root of the tree.
   • If both p and q have values greater than the root’s value, move to the right subtree.
   • If both p and q have values less than the root’s value, move to the left subtree.
   • If p and q are on different sides of the root, or one of them is equal to the root, then the root is their lowest common ancestor.

This approach ensures that we don’t need to search the entire tree, making it efficient.

Code

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode current = root;
        
        while (current != null) {
            if (p.val < current.val && q.val < current.val) {
                // Both nodes are in the left subtree
                current = current.left;
            } else if (p.val > current.val && q.val > current.val) {
                // Both nodes are in the right subtree
                current = current.right;
            } else {
                // We have found the split point
                return current;
            }
        }
        
        return null; // This should never be reached if p and q are guaranteed to be in the BST
    }
}

Time Complexity

• Best Case: (O(1)) if root itself is the lowest common ancestor.
• Average Case: (O(\log n)) for balanced BST, as we discard half of the tree at each step.
• Worst Case: (O(n)) in the case of a skewed BST (effectively a linked list).

Space Complexity

• O(1) because we are using a constant amount of space aside from the input data structure. There is no recursion depth or auxiliary data structure used.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?