Lowest Common Ancestor of a Binary Search Tree

Problem Statement

In this problem, we are provided with a binary search tree (BST) and two distinct nodes referred to as p and q. The task is to determine the lowest common ancestor (LCA) of these nodes within the tree. The LCA is defined as the lowest (i.e., deepest in terms of the tree structure) node of T that serves as an ancestor to both p and q. Notably, in terms of descendantship, nodes can be considered as their own descendants. Understanding this definition is crucial as it will directly influence how we approach the problem and implement the solution.

Examples

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.

Approach and Intuition

Given the properties of a BST, where the left child node's value is less than the parent node’s value and the right child's value is greater, we can efficiently determine the LCA. Here is the approach based on the structure and properties of the BST:

1. Start at the Root: Begin the search with the root node.
   • If both p and q are greater than the root node's value, this means both nodes reside in the right subtree. Thus, move to the right child of the node and continue the search.
   • If both are less than the root's value, move to the left child since both nodes would be in the left subtree.
   • If one node value is greater and the other less than the current node’s value, or one of them matches the current node's value, then the current node is the LCA.

Here’s how this approach directly ties into the examples provided:

• Example 1:

  • Nodes sought are 2 and 8.
  • Starting from node 6 (the root), since 2 is less than 6 and 8 is greater, node 6 is the LCA.

• Example 2:

  • Nodes sought are 2 and 4.
  • Both are less than the root (6), so we move to the left child that is node 2. Given 4 is greater than 2 and there is no further left child from 2, node 2 itself is the LCA.

• Example 3:

  • The nodes sought are 2 and 1.
  • Both values are from the root (2) and its left subtree, thus here also node 2 serves as the LCA.

These explanations support the structure and logic behind the outlined approach, capitalizing on BST properties to ensure optimal search efficiency.

Solutions

class Solution {
    public TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        int valueP = p.val;
        int valueQ = q.val;
        TreeNode currentNode = root;
    
        while (currentNode != null) {
            int currentValue = currentNode.val;
    
            if (valueP > currentValue && valueQ > currentValue) {
                currentNode = currentNode.right;
            } else if (valueP < currentValue && valueQ < currentValue) {
                currentNode = currentNode.left;
            } else {
                return currentNode;
            }
        }
        return null;
    }
}