Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree - Problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA: "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)."

Key Properties:

All nodes in the left subtree have values less than the root
All nodes in the right subtree have values greater than the root
We can use these properties to efficiently navigate the tree

Input & Output

Example 1 — Different Subtrees

$ Input: root = [6,2,8,0,4,7,9], p = 2, q = 8

› Output: 6

💡 Note: The LCA of nodes 2 and 8 is 6. Node 2 is in the left subtree and node 8 is in the right subtree of node 6, making 6 the lowest common ancestor.

Example 2 — Same Subtree

$ Input: root = [6,2,8,0,4,7,9], p = 2, q = 4

› Output: 2

💡 Note: The LCA of nodes 2 and 4 is 2. Since node 4 is a descendant of node 2, and we allow a node to be a descendant of itself, the LCA is 2.

Example 3 — Root as LCA

$ Input: root = [2,1,3], p = 1, q = 3

› Output: 2

💡 Note: The LCA of nodes 1 and 3 is 2. Node 1 is in the left subtree and node 3 is in the right subtree, so root 2 is their lowest common ancestor.

Constraints

The number of nodes in the tree is in the range [2, 10⁵]
-10⁹ ≤ Node.val ≤ 10⁹
All Node.val are unique
p ≠ q
p and q will exist in the BST

Visualization

Tap to expand

Understanding the Visualization

Input

BST with nodes and two target values p=2, q=8

Process

Navigate using BST property: compare targets with current node

Output

Return the value of the lowest common ancestor

Key Takeaway

🎯 Key Insight: Use BST ordering property - when targets are on different sides of current node, you've found the LCA

Asked in

a Amazon 45 M Microsoft 38 G Google 35 f Facebook 28

The key insight is leveraging BST properties where left nodes are smaller and right nodes are larger than their parent. The optimal approach navigates directly to the LCA by checking if both target nodes are on the same side or different sides of the current node. Time: O(h), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Node	O(n²)	O(h)	Check each node to see if it's an ancestor of both target nodes
Optimal BST Navigation	O(h)	O(1)	Use BST properties to navigate directly to LCA in one pass
Path Comparison Approach	O(h)	O(h)	Find paths from root to each node, then compare to find divergence point

Brute Force - Check Every Node — Algorithm Steps

Step 1: Traverse all nodes in the tree
Step 2: For each node, check if both p and q exist in its subtree
Step 3: Return the lowest node that contains both

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Root

Does node 6 contain both 2 and 8? Yes - continue deeper

Check Children

Check left subtree (2) and right subtree (8) recursively

Find LCA

Node 6 is the lowest node containing both 2 and 8

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

bool contains(struct TreeNode* node, int target) {
    if (!node) return false;
    if (node->val == target) return true;
    return contains(node->left, target) || contains(node->right, target);
}

struct TreeNode* findLCA(struct TreeNode* node, int p, int q) {
    if (!node) return NULL;
    
    if (contains(node, p) && contains(node, q)) {
        struct TreeNode* leftLCA = findLCA(node->left, p, q);
        struct TreeNode* rightLCA = findLCA(node->right, p, q);
        
        if (leftLCA) return leftLCA;
        if (rightLCA) return rightLCA;
        
        return node;
    }
    
    return NULL;
}

int solution(struct TreeNode* root, int p, int q) {
    return findLCA(root, p, q)->val;
}

struct TreeNode* newNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int main() {
    // Simplified parsing for demo
    struct TreeNode* root = newNode(6);
    root->left = newNode(2);
    root->right = newNode(8);
    root->left->left = newNode(0);
    root->left->right = newNode(4);
    
    int p = 2, q = 8;
    int result = solution(root, p, q);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we perform a subtree search that could visit all n nodes

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

156.0K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Node — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler