Lowest Common Ancestor of a Binary Search Tree medium

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).”

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.

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,null,null,null,null,null,null], 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,null,null,null,null,null,null], 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.

Steps

The key to solving this problem efficiently lies in leveraging the properties of a Binary Search Tree. In a BST, the values of nodes in the left subtree are smaller than the root's value, and the values of nodes in the right subtree are larger.

  1. Base Case: If the root is null, there's no LCA, so return null.
  2. Check if root is p or q: If the root is either p or q, we've found one of the nodes. The LCA will be either the root itself or the other node (which will be found in the subtree).
  3. Compare values:
    • If both p and q are smaller than the root's value, the LCA must be in the left subtree. Recursively call the function on the left subtree.
    • If both p and q are larger than the root's value, the LCA must be in the right subtree. Recursively call the function on the right subtree.
    • Otherwise (one value is smaller and the other is larger than the root's value), the root itself is the LCA.

Explanation

The algorithm efficiently searches for the LCA by exploiting the ordered nature of the BST. By comparing the values of p and q with the root's value, we can immediately eliminate one entire half of the tree, significantly reducing the search space. This recursive approach ensures we explore only the necessary parts of the tree until we find the LCA.

Code

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        if (root.val == p.val || root.val == q.val) return root;

        if (p.val < root.val && q.val < root.val) {
            return LowestCommonAncestor(root.left, p, q);
        } else if (p.val > root.val && q.val > root.val) {
            return LowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
}

Complexity

  • Time Complexity: O(H), where H is the height of the BST. In the worst case (a skewed BST), H could be equal to N (number of nodes), but in a balanced BST, H is log(N).
  • Space Complexity: O(H) due to the recursive call stack. In the worst case (a skewed BST), this could be O(N), but in a balanced BST, it's O(log N).