Lowest Common Ancestor

LCA in BST and binary trees with parent pointers.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

LCA in BST

In BST, use property: if both nodes < current, LCA in left; if both > current, LCA in right; otherwise current is LCA.

Golca-in-bst.go

13 linesLn 1, Col 1Go

BST property gives O(h) without recursion. p and q on different sides (or one equals root) → root is LCA.

LCA in Binary Tree

Recursive: if root is p or q, return root. Recurse left/right. If both non-nil, root is LCA. If one non-nil, return that (found p or q in subtree).

Golca-in-binary-tree.go

15 linesLn 1, Col 1Go

Postorder: process children first. If p,q found in different subtrees, current is LCA. If only one found, bubble it up.

LCA with Parent Pointers

If nodes have parent pointers, find LCA by climbing up. Method 1: HashSet of p's ancestors, climb q. Method 2: Two pointers, switch to other's start when reaching root (like intersection of linked lists).

Golca-with-parent-pointers-(two-pointer).go

17 linesLn 1, Col 1Go

a climbs p's ancestors then q's. b climbs q's then p's. They meet at LCA because total path lengths equal: dist(p,LCA)+dist(q,LCA) = dist(q,LCA)+dist(p,LCA).

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.