Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Lowest Common Ancestor
DSA

Lowest Common Ancestor

Understand techniques for finding the lowest common ancestor in binary trees and related structures.

LCA is the deepest node that is an ancestor of both given nodes. The core insight:

If left subtree has one target and right subtree has the other → current node is the LCA.

Focus on recognizing:

“Common ancestor” + “Two nodes in tree” + “Distance between nodes” = LCA

Pattern Table

PatternTypical QuestionsTrigger
Basic LCAFind common ancestorLeft has one, right has the other
LCA with Parent PointerParent references availableClimb up to match
Distance Between NodesNumber of edges between nodesdepth(a) + depth(b) - 2 * depth(lca)

Mental Trigger

DFS returns target node or null → If both left and right return non-null, current is LCA.

1. Generic Java LCA Template (Base)

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q)
        return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null)
        return root;

    return left != null ? left : right;
}
def lowest_common_ancestor(root, p, q):
    if root is None or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root

    return left if left else right
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr || root == p || root == q)
        return root;

    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if (left != nullptr && right != nullptr)
        return root;

    return left != nullptr ? left : right;
}
function lowestCommonAncestor(root, p, q) {
  if (root === null || root === p || root === q)
    return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left !== null && right !== null)
    return root;

  return left !== null ? left : right;
}

Everything else in LCA is just a modification of this template.

Pattern 1: LCA of BST

The split point — targets on different sides — IS the ancestor. Press ▶ to animate.

Lowest Common Ancestor In A BST

Find the LCA of two nodes in a BST.

Walk from the root: if both targets are smaller go left, both larger go right; the first node where they split (one on each side, or the node equals one target) is the LCA. BST ordering does the work in O(h) with no parent pointers.

TREE VISUALIZER
Steps –
62804
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        while root:
                      
                        2
                          both < root → go left
                      
                        3
                          both > root → go right
                      
                        4
                          else → SPLIT = answer

Java Code

public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > p.val && root.val > q.val)
        return lowestCommonAncestorBST(root.left, p, q);

    if (root.val < p.val && root.val < q.val)
        return lowestCommonAncestorBST(root.right, p, q);

    return root;
}
def lowest_common_ancestor_bst(root, p, q):
    if root.val > p.val and root.val > q.val:
        return lowest_common_ancestor_bst(root.left, p, q)

    if root.val < p.val and root.val < q.val:
        return lowest_common_ancestor_bst(root.right, p, q)

    return root
TreeNode* lowestCommonAncestorBST(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root->val > p->val && root->val > q->val)
        return lowestCommonAncestorBST(root->left, p, q);

    if (root->val < p->val && root->val < q->val)
        return lowestCommonAncestorBST(root->right, p, q);

    return root;
}
function lowestCommonAncestorBST(root, p, q) {
  if (root.val > p.val && root.val > q.val)
    return lowestCommonAncestorBST(root.left, p, q);

  if (root.val < p.val && root.val < q.val)
    return lowestCommonAncestorBST(root.right, p, q);

  return root;
}

What Changed from the Base Template?

BST property eliminates branches

Base:

// check both subtrees recursively

Changed:

if (root.val > p.val && root.val > q.val)
    return lowestCommonAncestorBST(root.left, p, q);

because in BST, if both nodes are smaller than root, LCA must be in the left subtree.

LCA in BST = Compare values + Go left if both smaller, right if both larger.

Pattern 2: Distance Between Two Nodes

d(p) + d(q) − 2·d(LCA): shared ancestry cancels out. Press ▶ to animate.

Distance Between Two Nodes

Compute the number of edges between two nodes using their lowest common ancestor.

Walk down from the root to find the LCA (the split node where the two targets diverge), then distance = d(p,LCA) + d(q,LCA), equivalently depth(p)+depth(q)−2·depth(LCA). Works for plain binary trees once LCA is found.

TREE VISUALIZER
Steps –
20822412
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        LCA = split node of (4, 7)
                      
                        2
                        d(n, LCA) via BST walk
                      
                        3
                        answer = d(4,L) + d(7,L)

Java Code

public int distance(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode lca = lowestCommonAncestor(root, p, q);
    return depth(root, lca) + depth(root, p) + depth(root, q) - 2 * depth(root, lca);
}

// ponytail: distance = depth(p) + depth(q) - 2 * depth(lca)
def distance(root, p, q):
    lca = lowest_common_ancestor(root, p, q)
    return depth(root, lca) + depth(root, p) + depth(root, q) - 2 * depth(root, lca)
int distance(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* lca = lowestCommonAncestor(root, p, q);
    return depth(root, lca) + depth(root, p) + depth(root, q) - 2 * depth(root, lca);
}
function distance(root, p, q) {
  const lca = lowestCommonAncestor(root, p, q);
  return depth(root, lca) + depth(root, p) + depth(root, q) - 2 * depth(root, lca);
}

What Changed from the Base Template?

Distance formula

Added:

int dist = depth(root, p) + depth(root, q) - 2 * depth(root, lca);

because the path from p to q goes up from p to LCA then down to q.

Distance = depth(p) + depth(q) - 2 * depth(lca).

LCA Pattern Evolution

Basic LCA (DFS + left/right return checks)
    ↓
LCA in BST
    (+ value comparison + single branch descent)
    ↓
Distance Between Nodes
    (+ LCA + depth formula)

Common Mistakes

Not handling the case where one node is ancestor of the other.

Basic LCA handles this: if root == p, return root before recursing.

Confusing LCA with common ancestor in BST.

BST LCA is simpler — compare values, no need for full DFS.

Using O(n) depth calculation repeatedly.

For single query, O(n) is fine. For multiple queries, precompute depths or use binary lifting.

Recognition Cheat Sheet

If you see…Think…
Common ancestor of two nodesLCA via DFS
BST + common ancestorBST LCA (value compare)
Distance between nodesLCA + depth formula
Multiple LCA queriesBinary lifting (preprocess)

My Private Notes

Notes are auto-saved locally to this device.