Tree Topology: Lowest Common Ancestor (LCA) and Tree Diameter Algorithms
Solve structural tree problems through post-order recursion invariants: computing Lowest Common Ancestor (LCA) and the diameter (longest path) of a binary tree.
By the end, you’ll be able to…
- Formulate post-order recursive invariants to identify Lowest Common Ancestor in binary trees
- Calculate the diameter of a binary tree in O(n) time by capturing cross-node path sum invariants
- Contrast LCA implementations between general binary trees and Binary Search Trees (BST)
01The Lowest Common Ancestor (LCA) Invariant
The Lowest Common Ancestor (LCA) of two nodes p and q in a tree is defined as the lowest node T that has both p and q as descendants (where we allow a node to be a descendant of itself). LCA is a core primitive in network routing, phylogenetic evolutionary biology, and DOM event dispatching.
In a general binary tree (without BST ordering), we solve LCA using bottom-up post-order traversal. At any node root: 1. If root is null, return null. 2. If root is either p or q, return root (we found one of the targets).
3. Recursively search the left and right subtrees. If both left and right return non-null, it means p is in one subtree and q is in the other—making root the lowest common ancestor! If only one subtree returns non-null, propagate that non-null result upward.
02Diameter of a Binary Tree: Longest Path Sum
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The diameter path passing through a specific node has length: height(leftSubtree) + height(rightSubtree). To find the global diameter, we must compute this sum for every node in the tree.
A naive solution computes height(node) for every node, taking O(n^2) time. By using bottom-up post-order recursion, we compute height and update the maximum diameter simultaneously in a single pass, achieving optimal O(n) runtime.
03LCA in Binary Search Trees (BST): Exploiting Ordering
When the tree is a Binary Search Tree (BST), we do not need to search both subtrees. The ordering property (left.val < root.val < right.val) allows us to locate LCA in O(h) time without inspecting unneeded branches:
1. If both p.val and q.val are strictly less than root.val, the LCA must reside entirely in the left subtree.
2. If both p.val and q.val are strictly greater than root.val, the LCA must reside entirely in the right subtree.
3. The first node where p and q split (one <= root and one >= root) is guaranteed to be the LCA!
04Complexity Comparison Table
Understanding algorithmic complexity differences between general binary trees and specialized BSTs is critical for interview and production performance:
Notice that BST ordering reduces traversal from exhaustive linear scans to targeted root-to-leaf path searches.
+--------------------+------------------+------------------+-----------------------+| Problem | Tree Type | Time Complexity | Auxiliary Space |+--------------------+------------------+------------------+-----------------------+| LCA | General Binary | O(n) | O(h) call stack || LCA | Binary Search T. | O(h) | O(1) iterative || Tree Diameter | General Binary | O(n) | O(h) call stack || Maximum Path Sum | General Binary | O(n) | O(h) call stack |+--------------------+------------------+------------------+-----------------------+The ideas worth keeping.
- Post-order traversal enables bottom-up propagation of subtree presence for LCA discovery.
- Binary tree diameter equals the maximum of leftHeight + rightHeight across all nodes.
- BST ordering reduces LCA search to a single root-to-leaf path exploration in O(h) time.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Implement an iterative LCA algorithm for a Bi
Implement an iterative LCA algorithm for a Binary Search Tree (BST) that runs in O(h) time and O(1) space.
Explore a worked solution
public class BSTLcaIterative { public static TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) { TreeNode curr = root; while (curr != null) { if (p.val < curr.val && q.val < curr.val) { curr = curr.left; } else if (p.val > curr.val && q.val > curr.val) { curr = curr.right; } else { return curr; // Split point or match found! } } return null; }}Iterate down the tree: move left if both values are smaller, move right if both values are larger.
Exercise 2: Explain why the diameter of a tree might not
Explain why the diameter of a tree might not pass through the root node, and provide an example.
Explore a worked solution
// If the left subtree has two very deep branches while the right subtree is shallow or empty,// the longest path between two leaf nodes can lie entirely within the left subtree.// For example: A root has right = null, and left has two subtrees each of depth 10.// The longest path (length 20) connects the two deep leaves in the left subtree without visiting root.Consider an unbalanced tree where one subtree is overwhelmingly deep.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Implement an iterative LCA algorithm for a Bi
Implement an iterative LCA algorithm for a Binary Search Tree (BST) that runs in O(h) time and O(1) space.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.