AtticDSATrees
Problem Patterns & Algorithms
Canonical solutions for maximum depth, diameter, LCA, path sum, invert tree, and subtree serialization
Most technical interview tree problems reduce to a handful of reusable recursive archetypes. Mastering these canonical patterns allows you to solve dozens of LeetCode / OA tree questions effortlessly.
Pattern 1: Height & Diameter Accumulation (Postorder)
When an answer requires information from both children before deciding the parent's answer, use postorder bottom-up recursion with a global accumulator variable.
1. Maximum Depth of Binary Tree
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}2. Diameter of Binary Tree
The diameter is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
public class Solution {
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDiameter = 0;
calculateHeight(root);
return maxDiameter;
}
private int calculateHeight(TreeNode node) {
if (node == null) return 0;
int leftHeight = calculateHeight(node.left);
int rightHeight = calculateHeight(node.right);
// Path passing through this node has length (leftHeight + rightHeight)
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
// Return height of current node to its parent
return 1 + Math.max(leftHeight, rightHeight);
}
}3. Binary Tree Maximum Path Sum
Find the maximum path sum of any non-empty path:
public class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxSum = Integer.MIN_VALUE;
gainFromSubtree(root);
return maxSum;
}
private int gainFromSubtree(TreeNode node) {
if (node == null) return 0;
// Ignore negative paths by taking Math.max(0, ...)
int leftGain = Math.max(0, gainFromSubtree(node.left));
int rightGain = Math.max(0, gainFromSubtree(node.right));
// Path passing through node combining both subtrees
maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
// Return maximum single branch path to parent
return node.val + Math.max(leftGain, rightGain);
}
}Pattern 2: Lowest Common Ancestor (General Binary Tree)
Find the lowest node that has both p and q as descendants:
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Base condition: reached leaf, or found p or 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 both left and right return non-null, p and q are in separate subtrees -> root is LCA!
if (left != null && right != null) {
return root;
}
// Otherwise, propagate the non-null result upward
return left != null ? left : right;
}Pattern 3: Tree Symmetry & Transformations
1. Invert / Flip Binary Tree
Swap left and right children recursively at every node:
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}2. Symmetric Tree (Mirror Image)
Check if a tree is a mirror of itself around the center:
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val) &&
isMirror(t1.left, t2.right) &&
isMirror(t1.right, t2.left);
}Pattern 4: Root-to-Leaf Path Search (Backtracking)
1. Path Sum (Target Existence)
Check if any root-to-leaf path sums to targetSum:
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
// Check leaf condition
if (root.left == null && root.right == null) {
return targetSum == root.val;
}
int remaining = targetSum - root.val;
return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}2. Path Sum II (Collect All Valid Paths)
Backtracking pattern with path list push and pop:
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> allPaths = new ArrayList<>();
findPaths(root, targetSum, new ArrayList<>(), allPaths);
return allPaths;
}
private void findPaths(TreeNode node, int sum, List<Integer> current, List<List<Integer>> allPaths) {
if (node == null) return;
current.add(node.val);
if (node.left == null && node.right == null && sum == node.val) {
allPaths.add(new ArrayList<>(current)); // Snapshot path
} else {
findPaths(node.left, sum - node.val, current, allPaths);
findPaths(node.right, sum - node.val, current, allPaths);
}
current.remove(current.size() - 1); // Backtrack
}Pattern 5: Tree Serialization & Deserialization
Encode a binary tree into a string and reconstruct the original tree object:
public class Codec {
private static final String SPLIT = ",";
private static final String NULL_NODE = "#";
// Encodes a tree to a single string (Preorder with # sentinels)
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildString(root, sb);
return sb.toString();
}
private void buildString(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NULL_NODE).append(SPLIT);
return;
}
sb.append(node.val).append(SPLIT);
buildString(node.left, sb);
buildString(node.right, sb);
}
// Decodes your encoded data to tree
public TreeNode deserialize(String data) {
Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(SPLIT)));
return buildTree(nodes);
}
private TreeNode buildTree(Queue<String> nodes) {
String val = nodes.poll();
if (val == null || val.equals(NULL_NODE)) return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = buildTree(nodes);
node.right = buildTree(nodes);
return node;
}
}Quick Problem Archetype Cheat Sheet
| Problem Goal | Strategy / Traversal | Time | Space |
|---|---|---|---|
| Max Depth / Height | Postorder DFS (1 + Math.max(left, right)) | O(n) | O(h) |
| Diameter | Postorder DFS with global max tracker | O(n) | O(h) |
| LCA (Binary Tree) | Postorder DFS returning non-null nodes | O(n) | O(h) |
| LCA (BST) | Iterative search comparing p and q to current node | O(h) | O(1) |
| Sorted Values from Tree | Inorder DFS on BST | O(n) | O(h) |
| Level Min / Max / Average | BFS Queue with levelSize = queue.size() snapshot | O(n) | O(w) |
| Path Sum Collection | Preorder DFS + Backtracking list push/pop | O(n) | O(h) |