Lowest Common Ancestor of a Binary Search Tree (LC 235): Split Point

Find the lowest common ancestor of two nodes in a BST. Walk down from the root: go left while both values are smaller, right while both are larger, and stop where they split. O(h) time, O(1) space.

Language Selection

Choose your preferred programming language

Showing: Python

Lowest Common Ancestor of a Binary Search Tree

Problem Statement

You are given the root of a binary search tree and two nodes p and q that are both in the tree. Return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as part of its own subtree, so if p is an ancestor of q, the answer is p itself.

In a binary search tree, every value in a node’s left subtree is smaller than the node’s value and every value in its right subtree is larger.

Examples

The tree used in the examples (level order [8,4,12,2,6,10,14,1,3,5,7]):

            8
         /     \
        4       12
       / \     /  \
      2   6   10   14
     / \ / \
    1  3 5  7

Example 1:

Input: root = [8,4,12,2,6,10,14,1,3,5,7], p = 2, q = 7
Output: 4
Explanation: 2 is in the left subtree of 4 and 7 is in its right subtree, so 4 is where their paths split.

Example 2:

Input: root = [8,4,12,2,6,10,14,1,3,5,7], p = 6, q = 5
Output: 6
Explanation: 5 is a child of 6, and a node is allowed to be an ancestor of itself.

Example 3:

Input: root = [8,4,12,2,6,10,14,1,3,5,7], p = 3, q = 14
Output: 8
Explanation: 3 is on the left of the root and 14 is on the right, so the root is the answer.

Constraints

  • The tree has between 2 and 10^5 nodes
  • -10^9 <= Node.val <= 10^9
  • All node values are distinct, and the tree is a valid BST
  • p != q, and both p and q exist in the tree

Approach 1: Compare Root-to-Node Paths

Algorithm

Because the tree is a BST, the path from the root to any value is forced: compare and go left or right. The lowest common ancestor is the last node the two paths share.

  1. Walk from the root to p, recording every node on the way (including p).
  2. Do the same for q.
  3. Step through both paths together from the root. The last position where they hold the same node is the answer.

Implementation

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def path_to(target):
            # The BST ordering decides each step, so no search is needed
            path = []
            node = root
            while node.val != target.val:
                path.append(node)
                node = node.left if target.val < node.val else node.right
            path.append(node)
            return path

        path_p = path_to(p)
        path_q = path_to(q)
        lca = root
        # Both paths start at the root; the last shared node is the answer
        for a, b in zip(path_p, path_q):
            if a is not b:
                break
            lca = a
        return lca

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.ArrayList;
import java.util.List;

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = pathTo(root, p);
        List<TreeNode> pathQ = pathTo(root, q);
        TreeNode lca = root;
        // Both paths start at the root; the last shared node is the answer
        for (int i = 0; i < pathP.size() && i < pathQ.size(); i++) {
            if (pathP.get(i) != pathQ.get(i)) break;
            lca = pathP.get(i);
        }
        return lca;
    }

    private List<TreeNode> pathTo(TreeNode root, TreeNode target) {
        // The BST ordering decides each step, so no search is needed
        List<TreeNode> path = new ArrayList<>();
        TreeNode node = root;
        while (node.val != target.val) {
            path.add(node);
            node = target.val < node.val ? node.left : node.right;
        }
        path.add(node);
        return path;
    }
}

Go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// The BST ordering decides each step, so no search is needed
	pathTo := func(target *TreeNode) []*TreeNode {
		path := []*TreeNode{}
		node := root
		for node.Val != target.Val {
			path = append(path, node)
			if target.Val < node.Val {
				node = node.Left
			} else {
				node = node.Right
			}
		}
		return append(path, node)
	}

	pathP, pathQ := pathTo(p), pathTo(q)
	lca := root
	// Both paths start at the root; the last shared node is the answer
	for i := 0; i < len(pathP) && i < len(pathQ); i++ {
		if pathP[i] != pathQ[i] {
			break
		}
		lca = pathP[i]
	}
	return lca
}

JavaScript:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    // The BST ordering decides each step, so no search is needed
    const pathTo = (target) => {
        const path = [];
        let node = root;
        while (node.val !== target.val) {
            path.push(node);
            node = target.val < node.val ? node.left : node.right;
        }
        path.push(node);
        return path;
    };

    const pathP = pathTo(p);
    const pathQ = pathTo(q);
    let lca = root;
    // Both paths start at the root; the last shared node is the answer
    for (let i = 0; i < pathP.length && i < pathQ.length; i++) {
        if (pathP[i] !== pathQ[i]) break;
        lca = pathP[i];
    }
    return lca;
};

C#:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
using System.Collections.Generic;

public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = PathTo(root, p);
        List<TreeNode> pathQ = PathTo(root, q);
        TreeNode lca = root;
        // Both paths start at the root; the last shared node is the answer
        for (int i = 0; i < pathP.Count && i < pathQ.Count; i++) {
            if (pathP[i] != pathQ[i]) break;
            lca = pathP[i];
        }
        return lca;
    }

    private static List<TreeNode> PathTo(TreeNode root, TreeNode target) {
        // The BST ordering decides each step, so no search is needed
        var path = new List<TreeNode>();
        TreeNode node = root;
        while (node.val != target.val) {
            path.Add(node);
            node = target.val < node.val ? node.left : node.right;
        }
        path.Add(node);
        return path;
    }
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <vector>
using namespace std;

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> pathP = pathTo(root, p);
        vector<TreeNode*> pathQ = pathTo(root, q);
        TreeNode* lca = root;
        // Both paths start at the root; the last shared node is the answer
        for (size_t i = 0; i < pathP.size() && i < pathQ.size(); i++) {
            if (pathP[i] != pathQ[i]) break;
            lca = pathP[i];
        }
        return lca;
    }

private:
    vector<TreeNode*> pathTo(TreeNode* root, TreeNode* target) {
        // The BST ordering decides each step, so no search is needed
        vector<TreeNode*> path;
        TreeNode* node = root;
        while (node->val != target->val) {
            path.push_back(node);
            node = target->val < node->val ? node->left : node->right;
        }
        path.push_back(node);
        return path;
    }
};

Complexity Analysis

  • Time: O(h), where h is the height of the tree. Each path has at most h + 1 nodes, and comparing them is linear in their length. In a skewed tree h can be n.
  • Space: O(h) for the two stored paths.

Approach 2: Walk Down to the Split Point (Optimal)

Algorithm

The paths in Approach 1 are identical until the first node where p and q go in different directions, and that node is the answer. We can find it in one walk without storing anything:

  1. Start at the root.
  2. If both p.val and q.val are smaller than the current value, both nodes are in the left subtree, so move left.
  3. If both are larger, move right.
  4. Otherwise the values split here (one on each side), or the current node equals p or q. Either way, the current node is the lowest common ancestor; return it.

Only comparisons are used. The popular shortcut (root.val - p.val) * (root.val - q.val) > 0 overflows 32-bit integers when values are near ±10^9.

Implementation

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        node = root
        while node:
            if p.val < node.val and q.val < node.val:
                node = node.left      # both targets are on the left
            elif p.val > node.val and q.val > node.val:
                node = node.right     # both targets are on the right
            else:
                return node           # they split here, or node is p or q
        return None

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = root;
        while (node != null) {
            if (p.val < node.val && q.val < node.val) {
                node = node.left;      // both targets are on the left
            } else if (p.val > node.val && q.val > node.val) {
                node = node.right;     // both targets are on the right
            } else {
                return node;           // they split here, or node is p or q
            }
        }
        return null;
    }
}

Go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	node := root
	for node != nil {
		switch {
		case p.Val < node.Val && q.Val < node.Val:
			node = node.Left // both targets are on the left
		case p.Val > node.Val && q.Val > node.Val:
			node = node.Right // both targets are on the right
		default:
			return node // they split here, or node is p or q
		}
	}
	return nil
}

JavaScript:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    let node = root;
    while (node) {
        if (p.val < node.val && q.val < node.val) {
            node = node.left;      // both targets are on the left
        } else if (p.val > node.val && q.val > node.val) {
            node = node.right;     // both targets are on the right
        } else {
            return node;           // they split here, or node is p or q
        }
    }
    return null;
};

C#:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = root;
        while (node != null) {
            if (p.val < node.val && q.val < node.val) {
                node = node.left;      // both targets are on the left
            } else if (p.val > node.val && q.val > node.val) {
                node = node.right;     // both targets are on the right
            } else {
                return node;           // they split here, or node is p or q
            }
        }
        return null;
    }
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* node = root;
        while (node) {
            if (p->val < node->val && q->val < node->val) {
                node = node->left;      // both targets are on the left
            } else if (p->val > node->val && q->val > node->val) {
                node = node->right;     // both targets are on the right
            } else {
                return node;            // they split here, or node is p or q
            }
        }
        return nullptr;
    }
};

Complexity Analysis

  • Time: O(h). Each iteration moves one level down, so at most h + 1 nodes are visited. That is O(log n) for a balanced tree and O(n) for a skewed one.
  • Space: O(1). Only one pointer is kept; there is no recursion and no stored path.

Key Insights

  1. The BST property tells you which way to go. In a general binary tree (LC 236) you must search both subtrees; here a comparison rules one out at every step.
  2. The answer is the split point. The first node whose value lies between p.val and q.val (inclusive) is the lowest common ancestor. Every node above it has both targets on the same side, and no node below it has both targets in its subtree.
  3. “Inclusive” handles the ancestor case. If the current node equals p or q, neither strict comparison holds, so the walk stops there automatically.
  4. A recursive version is equally short (if both smaller: recurse left; if both larger: recurse right; else return root), but it uses O(h) stack, which is up to 10^5 frames on a skewed tree.

Edge Cases

  • p is an ancestor of q (Example 2): the walk stops at p.
  • p or q is the root: the first iteration returns the root.
  • Targets on opposite sides of the root (Example 3): the root is returned immediately.
  • Two-node tree: one node is the root and the other its child, so the root is the answer.
  • Skewed tree with 10^5 nodes: the loop runs up to 10^5 times with constant memory; a recursive solution may overflow the stack.
  • Values near ±10^9: comparisons are safe; subtracting and multiplying values is not.

Common Mistakes

  1. Solving the general binary tree version. The LC 236 approach works but ignores the ordering and always visits O(n) nodes.
  2. Overflow in the product trick. (node.val - p.val) * (node.val - q.val) can exceed 32-bit range. Use two comparisons.
  3. Assuming p.val < q.val. The inputs can come in either order; the “both smaller” / “both larger” checks are symmetric, so no swap is needed.
  4. Stopping only at strict betweenness. Using p.val < node.val < q.val as the stop condition misses the case where the node is one of the targets.
  5. Comparing node values to node objects. Compare p.val with node.val, not p with node.val.

Interview Tips

  1. Ask whether the tree is a BST and whether both nodes are guaranteed to exist; both facts shape the solution.
  2. Draw the tree and trace the walk for a pair on the same side and a pair on opposite sides.
  3. Explain why the first split node must be the lowest ancestor, not just a common one.
  4. Mention the iterative version uses O(1) space, and point out the overflow trap in the multiplication shortcut.
  5. If asked for the general binary tree, switch to the post-order search from LC 236.

Follow-up Questions

  1. What if the tree is a general binary tree? Use the recursive search that returns the node where p and q are found in different subtrees: O(n) time. See Lowest Common Ancestor of a Binary Tree.
  2. What if p or q might not be in the tree? After finding the split node, confirm that both values can be reached from it with a normal BST search; return null if either is missing.
  3. How would you answer many LCA queries on a static tree? Precompute with binary lifting (O(n log n) preprocessing, O(log n) per query) or an Euler tour with a sparse table (O(1) per query).
  4. What about the LCA of more than two nodes? Track the minimum and maximum of the target values and walk until the current value lies between them.