Trees | Tree Algorithms
Tree algorithms build on one decisive habit: define what a recursive call returns for its subtree. A call may return a boolean, a height, a best path value or a node reference; choosing that contract makes the combine step simple.
Postorder Aggregation
When a node needs information from both children, solve children first and combine at the parent. Height, diameter, balance and subtree sums are classic postorder aggregation problems.
Path-Specific State
A root-to-leaf path must keep only the current path's state. Add a node on entry and undo it on return so sibling branches do not inherit values from an unrelated path.
Lowest Common Ancestor
For a general binary tree, return the target node found in each subtree. When left and right both return non-null, the current node is the first shared ancestor.
Global Answer With Local Return
Some problems return one local value to the parent but update a global best using both child results. Diameter returns one downward height while recording a path that may pass through the current node.
Avoid Repeated Subtree Work
A naive balance check computes height again and again. Return a failure sentinel with the height so each node is processed once, converting quadratic skewed-tree work into linear time.
Worked Examples
Example 1: Lowest Common Ancestor
If the current node is a target, return it. Otherwise recurse into both children: two non-null returns meet at the LCA, while one non-null return propagates the found target upward.
Code
public class Main {
static class Node {
int value; Node left, right;
Node(int value) { this.value = value; }
}
static Node lca(Node root, Node first, Node second) {
if (root == null || root == first || root == second) return root;
Node left = lca(root.left, first, second);
Node right = lca(root.right, first, second);
if (left != null && right != null) return root;
return left != null ? left : right;
}
public static void main(String[] args) {
Node root = new Node(3);
root.left = new Node(5); root.right = new Node(1);
root.left.left = new Node(6); root.left.right = new Node(2);
System.out.println(lca(root, root.left.left, root.left.right).value);
}
}Expected Result
5
Example 2: Diameter of a Binary Tree
The helper returns downward height. At every node, leftHeight plus rightHeight counts the longest path that turns through that node, so update the global diameter before returning.
Code
public class Main {
static class Node {
Node left, right;
Node() { }
}
static int best = 0;
static int height(Node node) {
if (node == null) return 0;
int leftHeight = height(node.left);
int rightHeight = height(node.right);
best = Math.max(best, leftHeight + rightHeight);
return 1 + Math.max(leftHeight, rightHeight);
}
public static void main(String[] args) {
Node root = new Node();
root.left = new Node(); root.right = new Node();
root.left.left = new Node(); root.left.left.left = new Node();
height(root);
System.out.println(best);
}
}Expected Result
4
Example 3: Path Sum With Backtracking
The current path list is mutable but belongs to one DFS branch. Add the node before exploring, record a copy at a valid leaf, then remove the node before returning to the caller.
Code
import java.util.ArrayList;
import java.util.List;
public class Main {
static class Node {
int value; Node left, right;
Node(int value) { this.value = value; }
}
static void paths(Node node, int remaining, List<Integer> path, List<List<Integer>> answer) {
if (node == null) return;
path.add(node.value);
if (node.left == null && node.right == null && remaining == node.value) {
answer.add(new ArrayList<>(path));
} else {
paths(node.left, remaining - node.value, path, answer);
paths(node.right, remaining - node.value, path, answer);
}
path.remove(path.size() - 1);
}
public static void main(String[] args) {
Node root = new Node(5); root.left = new Node(4); root.right = new Node(8);
root.left.left = new Node(11); root.left.left.left = new Node(7);
List<List<Integer>> answer = new ArrayList<>();
paths(root, 27, new ArrayList<>(), answer);
System.out.println(answer);
}
}Expected Result
[[5, 4, 11, 7]]
Example 4: Linear-Time Balanced Tree Check
Return subtree height when balanced and -1 when unbalanced. A parent immediately propagates -1, so no subtree height is recalculated after imbalance has already been discovered.
Code
public class Main {
static class Node {
Node left, right;
}
static int checkedHeight(Node node) {
if (node == null) return 0;
int left = checkedHeight(node.left);
if (left == -1) return -1;
int right = checkedHeight(node.right);
if (right == -1 || Math.abs(left - right) > 1) return -1;
return 1 + Math.max(left, right);
}
static boolean isBalanced(Node root) {
return checkedHeight(root) != -1;
}
public static void main(String[] args) {
Node root = new Node();
root.left = new Node(); root.right = new Node();
root.left.left = new Node();
System.out.println(isBalanced(root));
}
}Expected Result
true
Complexity Analysis
| Operation | Complexity | Explanation |
|---|---|---|
| LCA in binary tree | O(n) time, O(h) stack space | The recursion visits each node at most once. |
| Diameter | O(n) time, O(h) stack space | A single postorder pass returns heights and updates the answer. |
| Root-to-leaf paths | O(n + output size) | Every node is visited; copied paths account for emitted output. |
Common Mistakes
- Returning a shared mutable path list instead of copying it when a valid leaf is reached.
- Calculating subtree height repeatedly in a separate balance check for every node.
- Using BST-specific LCA comparisons on a general binary tree without the ordering guarantee.
- Forgetting whether diameter is measured in edges or nodes when reporting the result.
Interview Checklist
- State the exact recursive return contract before writing child calls.
- Explain which result is local to a subtree and which result is global across the tree.
- Check a null root, a one-node tree, skewed depth and a path crossing the root.
- Show the backtracking undo step after every recursive path extension.
