Lowest Common Ancestor of a Binary Search Tree

Problem Statement

Given a binary search tree (BST) of unique values and two nodes p and q, return the lowest common ancestor (LCA) of the two nodes in the BST.

The lowest common ancestor between two nodes p and q is the lowest node in a tree T such that both p and q are descendants of node (where we allow a node to be a descendant of itself).

What to notice first

• The BST property guarantees a unique path from root to any node.
• If both p and q are less than the current node, the LCA is in the left subtree.
• If both p and q are greater than the current node, the LCA is in the right subtree.
• Otherwise, the current node is the LCA (they diverge here).

Examples

Input	p	q	Output	Explanation
Tree: 6, 2→8, 0, 4→7, 9, 3, 5	2	8	6	6 is the LCA of 2 and 8
Tree: 6, 2→8, 0, 4→7, 9, 3, 5	2	4	2	2 is the LCA of 2 and 4 (one node is ancestor of the other)
Tree: 2, 1, 3	1	3	2	2 is the LCA of 1 and 3

Constraints

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• Both p and q exist in the BST.

Real-World Applications

Where this pattern appears

• File system hierarchies — find the common parent directory of two files to determine shared permissions.
• Organizational structures — identify the smallest management unit responsible for two employees.
• Biological taxonomy — find the most recent common ancestor of two species in an evolutionary tree.
• Version control systems — determine the merge base between two branches in Git history.

Complexity Comparison

Approach	Time	Space	Key Idea	Best When
Recursive	O(log n) avg, O(n) worst	O(h)	Use BST property to prune search space	Standard — elegant, leverages BST structure
Iterative	O(log n) avg, O(n) worst	O(1)	Same logic without recursion stack	Memory-constrained, prefer iteration

Which approach should you learn first?

• Pick Recursive if you want clarity and simplicity (most interviewers prefer this).
• Pick Iterative if you want to optimize space or demonstrate understanding of iteration.

Standard & Elegant

Recursive

O(log n) avg · O(h) space

Space Optimized

Iterative

O(log n) avg · O(1) space

Approach 1: Recursive (Recommended)

★ Recommended

Leverage the BST property: compare current node value with both p and q. If both are smaller, recurse left. If both are larger, recurse right. Otherwise, the current node is the LCA.

The elegance comes from the fact that the BST structure guarantees a convergence point where the two nodes “split” — this point is the LCA.

⏱ Time O(log n) Binary search-like 💾 Space O(h) Recursion stack

Step-by-step Example

Input: BST with root = 6, p = 2, q = 8

Step	Current Node	p vs Node	q vs Node	Action
1	6	2 < 6	8 > 6	p and q on different sides → return 6

Result: LCA = 6 ✓

Input: BST with root = 6, p = 2, q = 4

Step	Current Node	p vs Node	q vs Node	Action
1	6	2 < 6	4 < 6	Both in left subtree → recurse left
2	2	2 == 2	4 > 2	p and q on different sides → return 2

Result: LCA = 2 ✓

Animated walkthrough

How recursive approach finds the LCA

Navigate down the tree using BST property. When p and q diverge (one left, one right), you've found the LCA.

Back Autoplay Next Reset

Step 1 of 2 Target: 6

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function lowestCommonAncestorRecursive(root, p, q):
    if root.val > p.val and root.val > q.val:
        // Both p and q are in left subtree
        return lowestCommonAncestorRecursive(root.left, p, q)
    elif root.val < p.val and root.val < q.val:
        // Both p and q are in right subtree
        return lowestCommonAncestorRecursive(root.right, p, q)
    else:
        // p and q are on different sides or one is root
        return root

Solution Code

Python

lowest_common_ancestor_bst_recursive.py

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def lowest_common_ancestor_recursive(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Recursive approach to find LCA in a BST.

    Exploit BST property: if both p and q are in left subtree, LCA is in left.
    If both in right subtree, LCA is in right. Otherwise, current node is LCA.

    Time: O(log n) average, O(n) worst case (skewed tree)
    Space: O(h) - recursion stack, h = height
    """
    if root.val > p.val and root.val > q.val:
        # Both p and q are in left subtree
        return lowest_common_ancestor_recursive(root.left, p, q)
    elif root.val < p.val and root.val < q.val:
        # Both p and q are in right subtree
        return lowest_common_ancestor_recursive(root.right, p, q)
    else:
        # p and q are on different sides or one of them is root
        return root


# Test cases
if __name__ == "__main__":
    # Example 1: LCA of 2 and 8 in tree [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
    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
    q = root.left.right
    result = lowest_common_ancestor_recursive(root, p, q)
    print(result.val)  # 2

    # Example 2: LCA of 2 and 4
    p = root.left
    q = root.left.right
    result = lowest_common_ancestor_recursive(root, p, q)
    print(result.val)  # 2

C++

lowest_common_ancestor_bst_recursive.cpp

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root->val > p->val && root->val > q->val) {
            // Both p and q are in left subtree
            return lowestCommonAncestor(root->left, p, q);
        } else if (root->val < p->val && root->val < q->val) {
            // Both p and q are in right subtree
            return lowestCommonAncestor(root->right, p, q);
        } else {
            // p and q are on different sides or one of them is root
            return root;
        }
    }
};

int main() {
    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);

    Solution sol;
    TreeNode* p = root->left;
    TreeNode* q = root->left->right;
    cout << sol.lowestCommonAncestor(root, p, q)->val << endl;  // 2

    return 0;
}

Java

LowestCommonAncestorBST_Recursive.java

public class LowestCommonAncestorBST_Recursive {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) {
            // Both p and q are in left subtree
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            // Both p and q are in right subtree
            return lowestCommonAncestor(root.right, p, q);
        } else {
            // p and q are on different sides or one of them is root
            return root;
        }
    }

    public static void main(String[] args) {
        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);

        LowestCommonAncestorBST_Recursive sol = new LowestCommonAncestorBST_Recursive();
        TreeNode p = root.left;
        TreeNode q = root.left.right;
        System.out.println(sol.lowestCommonAncestor(root, p, q).val);  // 2
    }
}

JavaScript

lowest_common_ancestor_bst_recursive.js

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

function lowestCommonAncestorRecursive(root, p, q) {
    if (root.val > p.val && root.val > q.val) {
        // Both p and q are in left subtree
        return lowestCommonAncestorRecursive(root.left, p, q);
    } else if (root.val < p.val && root.val < q.val) {
        // Both p and q are in right subtree
        return lowestCommonAncestorRecursive(root.right, p, q);
    } else {
        // p and q are on different sides or one of them is root
        return root;
    }
}

// Test cases
const 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);

const p = root.left;
const q = root.left.right;
console.log(lowestCommonAncestorRecursive(root, p, q).val);  // 2

Rust

lowest_common_ancestor_bst_recursive.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

pub fn lowest_common_ancestor_recursive(
    root: Option<Rc<RefCell<TreeNode>>>,
    p: &TreeNode,
    q: &TreeNode,
) -> Option<Rc<RefCell<TreeNode>>> {
    if let Some(node) = root {
        let node_ref = node.borrow();

        if node_ref.val > p.val && node_ref.val > q.val {
            // Both p and q are in left subtree
            let left = node_ref.left.clone();
            drop(node_ref);
            return lowest_common_ancestor_recursive(left, p, q);
        } else if node_ref.val < p.val && node_ref.val < q.val {
            // Both p and q are in right subtree
            let right = node_ref.right.clone();
            drop(node_ref);
            return lowest_common_ancestor_recursive(right, p, q);
        } else {
            // p and q are on different sides or one of them is current
            return Some(node);
        }
    }
    None
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(6)));
    let left = Rc::new(RefCell::new(TreeNode::new(2)));
    let right = Rc::new(RefCell::new(TreeNode::new(8)));

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right);

    let left_left = Rc::new(RefCell::new(TreeNode::new(0)));
    let left_right = Rc::new(RefCell::new(TreeNode::new(4)));

    left.borrow_mut().left = Some(left_left);
    left.borrow_mut().right = Some(left_right.clone());

    let left_right_left = Rc::new(RefCell::new(TreeNode::new(3)));
    let left_right_right = Rc::new(RefCell::new(TreeNode::new(5)));

    left_right.borrow_mut().left = Some(left_right_left);
    left_right.borrow_mut().right = Some(left_right_right);

    let p = left.borrow();
    let q = left_right.borrow();
    if let Some(result) = lowest_common_ancestor_recursive(Some(root), &*p, &*q) {
        println!("{}", result.borrow().val);  // 2
    }
}

Go

lowest_common_ancestor_bst_recursive.go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func LowestCommonAncestorRecursive(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
    if root.Val > p.Val && root.Val > q.Val {
        // Both p and q are in left subtree
        return LowestCommonAncestorRecursive(root.Left, p, q)
    } else if root.Val < p.Val && root.Val < q.Val {
        // Both p and q are in right subtree
        return LowestCommonAncestorRecursive(root.Right, p, q)
    } else {
        // p and q are on different sides or one of them is root
        return root
    }
}

func main() {
    root := &TreeNode{Val: 6}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 8}
    root.Left.Left = &TreeNode{Val: 0}
    root.Left.Right = &TreeNode{Val: 4}
    root.Left.Right.Left = &TreeNode{Val: 3}
    root.Left.Right.Right = &TreeNode{Val: 5}
    root.Right.Left = &TreeNode{Val: 7}
    root.Right.Right = &TreeNode{Val: 9}

    p := root.Left
    q := root.Left.Right
    fmt.Println(LowestCommonAncestorRecursive(root, p, q).Val)  // 2
}

Approach 2: Iterative

🎯 Interview Favourite

Same logic as the recursive approach, but implemented with a while loop instead of recursion. Navigate the tree by comparing node values with p and q, moving left or right until convergence.

This approach avoids the recursion stack entirely, useful when stack depth is a concern or when iterative solutions are preferred.

⏱ Time O(log n) Binary search-like 💾 Space O(1) No extra structure

Step-by-step Example

Same as Approach 1, but using a while loop instead of recursion:

Iteration	Current Node	p vs Node	q vs Node	Action
1	6	2 < 6	8 > 6	p and q on different sides → return 6

Pseudocode

function lowestCommonAncestorIterative(root, p, q):
    current = root
    while current is not null:
        if current.val > p.val and current.val > q.val:
            // Both in left subtree
            current = current.left
        elif current.val < p.val and current.val < q.val:
            // Both in right subtree
            current = current.right
        else:
            // Divergence point found
            return current
    return root

Solution Code

Python

lowest_common_ancestor_bst_iterative.py

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def lowest_common_ancestor_iterative(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Iterative approach to find LCA in a BST.

    Same logic as recursive but using a while loop.
    Leverage BST property to navigate toward convergence point.

    Time: O(log n) average, O(n) worst case (skewed tree)
    Space: O(1) - only using constant extra space
    """
    current = root

    while current:
        if current.val > p.val and current.val > q.val:
            # Both p and q are in left subtree
            current = current.left
        elif current.val < p.val and current.val < q.val:
            # Both p and q are in right subtree
            current = current.right
        else:
            # p and q are on different sides or one of them is current
            return current

    return root


# Test cases
if __name__ == "__main__":
    # Example 1: LCA of 2 and 8 in tree [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
    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
    q = root.left.right
    result = lowest_common_ancestor_iterative(root, p, q)
    print(result.val)  # 2

    # Example 2: LCA of 2 and 4
    p = root.left
    q = root.left.right
    result = lowest_common_ancestor_iterative(root, p, q)
    print(result.val)  # 2

C++

lowest_common_ancestor_bst_iterative.cpp

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* current = root;

        while (current) {
            if (current->val > p->val && current->val > q->val) {
                // Both p and q are in left subtree
                current = current->left;
            } else if (current->val < p->val && current->val < q->val) {
                // Both p and q are in right subtree
                current = current->right;
            } else {
                // p and q are on different sides or one of them is current
                return current;
            }
        }

        return root;
    }
};

int main() {
    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);

    Solution sol;
    TreeNode* p = root->left;
    TreeNode* q = root->left->right;
    cout << sol.lowestCommonAncestor(root, p, q)->val << endl;  // 2

    return 0;
}

Java

LowestCommonAncestorBST_Iterative.java

public class LowestCommonAncestorBST_Iterative {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode current = root;

        while (current != null) {
            if (current.val > p.val && current.val > q.val) {
                // Both p and q are in left subtree
                current = current.left;
            } else if (current.val < p.val && current.val < q.val) {
                // Both p and q are in right subtree
                current = current.right;
            } else {
                // p and q are on different sides or one of them is current
                return current;
            }
        }

        return root;
    }

    public static void main(String[] args) {
        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);

        LowestCommonAncestorBST_Iterative sol = new LowestCommonAncestorBST_Iterative();
        TreeNode p = root.left;
        TreeNode q = root.left.right;
        System.out.println(sol.lowestCommonAncestor(root, p, q).val);  // 2
    }
}

JavaScript

lowest_common_ancestor_bst_iterative.js

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

function lowestCommonAncestorIterative(root, p, q) {
    let current = root;

    while (current) {
        if (current.val > p.val && current.val > q.val) {
            // Both p and q are in left subtree
            current = current.left;
        } else if (current.val < p.val && current.val < q.val) {
            // Both p and q are in right subtree
            current = current.right;
        } else {
            // p and q are on different sides or one of them is current
            return current;
        }
    }

    return root;
}

// Test cases
const 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);

const p = root.left;
const q = root.left.right;
console.log(lowestCommonAncestorIterative(root, p, q).val);  // 2

Rust

lowest_common_ancestor_bst_iterative.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

pub fn lowest_common_ancestor_iterative(
    root: Option<Rc<RefCell<TreeNode>>>,
    p: &TreeNode,
    q: &TreeNode,
) -> Option<Rc<RefCell<TreeNode>>> {
    let mut current = root;

    while let Some(node) = current {
        let node_ref = node.borrow();

        if node_ref.val > p.val && node_ref.val > q.val {
            // Both p and q are in left subtree
            let left = node_ref.left.clone();
            drop(node_ref);
            current = left;
        } else if node_ref.val < p.val && node_ref.val < q.val {
            // Both p and q are in right subtree
            let right = node_ref.right.clone();
            drop(node_ref);
            current = right;
        } else {
            // p and q are on different sides or one of them is current
            return Some(node);
        }
    }

    None
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(6)));
    let left = Rc::new(RefCell::new(TreeNode::new(2)));
    let right = Rc::new(RefCell::new(TreeNode::new(8)));

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right);

    let left_left = Rc::new(RefCell::new(TreeNode::new(0)));
    let left_right = Rc::new(RefCell::new(TreeNode::new(4)));

    left.borrow_mut().left = Some(left_left);
    left.borrow_mut().right = Some(left_right.clone());

    let left_right_left = Rc::new(RefCell::new(TreeNode::new(3)));
    let left_right_right = Rc::new(RefCell::new(TreeNode::new(5)));

    left_right.borrow_mut().left = Some(left_right_left);
    left_right.borrow_mut().right = Some(left_right_right);

    let p = left.borrow();
    let q = left_right.borrow();
    if let Some(result) = lowest_common_ancestor_iterative(Some(root), &*p, &*q) {
        println!("{}", result.borrow().val);  // 2
    }
}

Go

lowest_common_ancestor_bst_iterative.go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func LowestCommonAncestorIterative(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {
    current := root

    for current != nil {
        if current.Val > p.Val && current.Val > q.Val {
            // Both p and q are in left subtree
            current = current.Left
        } else if current.Val < p.Val && current.Val < q.Val {
            // Both p and q are in right subtree
            current = current.Right
        } else {
            // p and q are on different sides or one of them is current
            return current
        }
    }

    return root
}

func main() {
    root := &TreeNode{Val: 6}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 8}
    root.Left.Left = &TreeNode{Val: 0}
    root.Left.Right = &TreeNode{Val: 4}
    root.Left.Right.Left = &TreeNode{Val: 3}
    root.Left.Right.Right = &TreeNode{Val: 5}
    root.Right.Left = &TreeNode{Val: 7}
    root.Right.Right = &TreeNode{Val: 9}

    p := root.Left
    q := root.Left.Right
    fmt.Println(LowestCommonAncestorIterative(root, p, q).Val)  // 2
}

Common mistakes

Watch for these pitfalls

• Forgetting the BST property: Treating it like a general binary tree and searching both subtrees. The BST allows pruning.
• Comparing with both p and q separately: Make sure you’re comparing the node value against both p.val and q.val, not node structure.
• Not handling the case where one node is the ancestor of another: If p = 2 and q = 4, and 2 is an ancestor of 4, then 2 is the LCA, not their “convergence.”
• Assuming convergence always happens at an internal node: The LCA can be one of the nodes themselves (p or q).

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

lowest_common_ancestor_of_a_binary_search_tree_space_optimized.py

def solution(): return 0

C++

lowest_common_ancestor_of_a_binary_search_tree_space_optimized.cpp

int main() {}

Java

LowestCommonAncestorOfABinarySearchTreeSpaceOptimized.java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

System.out.println("LCA Solution");

JavaScript

lowest_common_ancestor_of_a_binary_search_tree_space_optimized.js

function solution() { return 0; }
module.exports = solution;

Rust

lowest_common_ancestor_of_a_binary_search_tree_space_optimized.rs

fn main() {}

Go

lowest_common_ancestor_of_a_binary_search_tree_space_optimized.go

package main

Related Problems

• Validate Binary Search Tree ↗ Medium #98
• Kth Smallest Element in a BST ↗ Medium #230
• Lowest Common Ancestor of a Binary Tree ↗ Medium #236
• Minimum Absolute Difference in BST ↗ Easy #530

Interview Tips

Key trade-offs to discuss

• Why BST LCA is simpler than general tree LCA: The BST property creates a unique path to each node. You don’t need to search both subtrees; you can prune based on value comparisons.
• Recursive vs Iterative: Recursive is cleaner and more elegant. Iterative avoids stack overhead. Choose based on the interviewer’s preference or constraints.
• Edge cases: One node is the ancestor of another (still valid LCA), both nodes are the same node is not possible (p != q guaranteed), null checks are minimal due to problem constraints.
• Follow-up — General Binary Tree: If the interviewer changes it to a non-BST, explain how you’d store parent pointers or use DFS to find ancestors, then find the first common one.

← Previous
#234 Palindrome Linked List Next
#236 Lowest Common Ancestor of a Binary Tree →