Vultr DocsLatest Content

Lowest Common Ancestor of a Binary Search Tree

Updated on 05 June, 2025
Lowest Common Ancestor of a Binary Search Tree header image

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

  • Java
  • Python
java 
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;
    }
}

The provided Java program solves the problem of finding the lowest common ancestor (LCA) of two nodes in a Binary Search Tree (BST). This solution leverages the properties of the BST, where for each node, all the nodes in the left subtree are smaller and all the nodes in the right subtree are larger.

  • Start by storing the values of the two nodes p and q in valueP and valueQ respectively.
  • Initialize currentNode with the root of the BST.
  • Use a while loop to traverse the tree starting from the root. During each iteration, compare the current node's value with valueP and valueQ.
  • If both values are greater than the current node's value, move to the right child of the current node.
  • If both values are less than the current node's value, move to the left child.
  • If one value is greater and the other is less, or if the current node is equal to p or q, the current node is the LCA, and return this node.
  • If the traversal finishes without finding the LCA, return null.

This approach ensures that the algorithm efficiently finds the LCA with a time complexity of O(h), where h is the height of the BST, making it optimal for large trees.

python 
class Solution:
    def findLCA(self, root_node: TreeNode, node1: TreeNode, node2: TreeNode) -> TreeNode:
        # Values of node1 and node2
        val1 = node1.val
        val2 = node2.val

        # Initialize the start of tree traversal
        current_node = root_node

        # Continue traversing the binary tree
        while current_node:
            # Current node value
            current_val = current_node.val

            if val1 > current_val and val2 > current_val:
                # Move to the right if both target nodes are greater
                current_node = current_node.right
            elif val1 < current_val and val2 < current_val:
                # Move to the left if both target nodes are less
                current_node = current_node.left
            else:
                # LCA found where paths diverge
                return current_node

The solution addresses the problem of finding the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST). Utilizing Python, the implemented approach harnesses the properties of the BST to efficiently determine the LCA.

The function findLCA accepts three parameters:

  • root_node: the root of the BST
  • node1 and node2: the two nodes for which the LCA is to be found

The algorithm operates by comparing the values of node1 and node2 with the value of the current node starting from the root_node. Key steps include:

  1. Traverse the tree starting from the root.
  2. At each node, compare node1 and node2's values to the current node's value.
  3. If both values are greater than the current node's value, move to the right child of the current node.
  4. If both values are less than the current node's value, move to the left child of the current node.
  5. When one value is greater and the other is less than the current node’s value, or if the current node's value matches one of the nodes' values, the current node is the LCA.

This method leverages the fact that in a BST, all values to the left of a node are less than the node and all values to the right are greater, making it possible to efficiently find the divergence point where the paths to node1 and node2 split, which is the LCA. The method returns the LCA node once found. This solution is optimal for a BST, providing a time complexity of O(h) where h is the height of the tree.

Comments

No comments yet.