Lowest Common Ancestor in a BST

Given a binary search tree (BST) and two nodes p and q, write a program to find their Lowest Common Ancestor (LCA). The LCA of two nodes in a BST is the lowest (deepest) node that has both p and q as descendants (where a node can be a descendant of itself).

Input/Output Examples

plaintext
Example 1:
Input:
       6
      / \
     2   8
    / \ / \
   0  4 7  9
     / \
    3   5

p = 2, q = 8
Output: 6
Explanation: The lowest common ancestor of 2 and 8 is 6.

Example 2:
Input:
       6
      / \
     2   8
    / \ / \
   0  4 7  9
     / \
    3   5

p = 2, q = 4
Output: 2
Explanation: The lowest common ancestor of 2 and 4 is 2 itself, as a node can be its own ancestor.

Approach to Find the Lowest Common Ancestor in a BST

  1. Binary Search Tree Property:
    • In a BST, for any node N, all nodes in its left subtree are smaller than N, and all nodes in its right subtree are larger than N.
    • This property allows us to efficiently search for the LCA by comparing the values of p and q with the current node.
  2. Recursive Approach:
    • Start from the root of the tree. For each node:
      • If both p and q are smaller than the current node, the LCA must be in the left subtree.
      • If both p and q are greater than the current node, the LCA must be in the right subtree.
      • If p and q lie on opposite sides (i.e., one is smaller and the other is greater), then the current node is the LCA.
  3. Edge Case:
    • If p or q is the current node, then the current node is the LCA because a node can be its own ancestor.

C++ Program to Find the Lowest Common Ancestor in a BST

cpp
#include <iostream>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Function to find the lowest common ancestor in a BST
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL) {
        return NULL;
    }

    // If both p and q are smaller than root, LCA lies in the left subtree
    if (p->data < root->data && q->data < root->data) {
        return lowestCommonAncestor(root->left, p, q);
    }

    // If both p and q are greater than root, LCA lies in the right subtree
    if (p->data > root->data && q->data > root->data) {
        return lowestCommonAncestor(root->right, p, q);
    }

    // If p and q lie on opposite sides, the current node is the LCA
    return root;
}

int main() {
    // Create a sample BST
    TreeNode* root = new TreeNode(6);
    root->left = new TreeNode(2);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(4);
    root->left->right->left = new TreeNode(3);
    root->left->right->right = new TreeNode(5);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);

    TreeNode* p = root->left;    // Node with value 2
    TreeNode* q = root->right;   // Node with value 8

    // Find and print the lowest common ancestor
    TreeNode* lca = lowestCommonAncestor(root, p, q);
    if (lca != NULL) {
        cout << "Lowest Common Ancestor: " << lca->data << endl;
    } else {
        cout << "No common ancestor found." << endl;
    }

    return 0;
}

Java Program to Find the Lowest Common Ancestor in a BST

java
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

public class LCAInBST {

    // Function to find the lowest common ancestor in a BST
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        // If both p and q are smaller than root, LCA lies in the left subtree
        if (p.data < root.data && q.data < root.data) {
            return lowestCommonAncestor(root.left, p, q);
        }

        // If both p and q are greater than root, LCA lies in the right subtree
        if (p.data > root.data && q.data > root.data) {
            return lowestCommonAncestor(root.right, p, q);
        }

        // If p and q lie on opposite sides, the current node is the LCA
        return root;
    }

    public static void main(String[] args) {
        // Create a sample BST
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);

        TreeNode p = root.left;    // Node with value 2
        TreeNode q = root.right;   // Node with value 8

        // Find and print the lowest common ancestor
        TreeNode lca = lowestCommonAncestor(root, p, q);
        if (lca != null) {
            System.out.println("Lowest Common Ancestor: " + lca.data);
        } else {
            System.out.println("No common ancestor found.");
        }
    }
}

Python Program to Find the Lowest Common Ancestor in a BST

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to find the lowest common ancestor in a BST
def lowest_common_ancestor(root, p, q):
    if root is None:
        return None

    # If both p and q are smaller than root, LCA lies in the left subtree
    if p.data < root.data and q.data < root.data:
        return lowest_common_ancestor(root.left, p, q)

    # If both p and q are greater than root, LCA lies in the right subtree
    if p.data > root.data and q.data > root.data:
        return lowest_common_ancestor(root.right, p, q)

    # If p and q lie on opposite sides, the current node is the LCA
    return root

# Example usage
if __name__ == "__main__":
    # Create a sample BST
    root = TreeNode(6)
    root.left = TreeNode(2)
    root.right = TreeNode(8)
    root.left.left = TreeNode(0)
    root.left.right = TreeNode(4)
    root.left.right.left = TreeNode(3)
    root.left.right.right = TreeNode(5)
    root.right.left = TreeNode(7)
    root.right.right = TreeNode(9)

    p = root.left   # Node with value 2
    q = root.right  # Node with value 8

    # Find and print the lowest common ancestor
    lca = lowest_common_ancestor(root, p, q)
    if lca is not None:
        print("Lowest Common Ancestor:", lca.data)
    else:
        print("No common ancestor found.")
  • Time Complexity: O(h), where h is the height of the binary search tree. In the worst case, this could be O(n) for a skewed tree, but for a balanced BST, it is O(log n).
  • Space Complexity: O(h) due to the recursive call stack. In the worst case, this can be O(n).

DSA

7890

563

Related Articles