Goal: master every problem that reduces to computing height/depth or uses height as the main building block. After this read, you should immediately recognise the pattern, apply the template, and adapt it to variations interviewers throw at you.
🔍 How to identify this pattern
Look for keywords in the prompt:
- height, depth, max depth, minimum depth
- balanced, balanced binary tree
- diameter, longest path
- longest/univalue path, max path sum, height of tree If the question asks for longest/shortest distance, a property that depends on left/right subtree heights, or uses "longest" or "height" in any way — height/depth recursion is likely the right pattern.
🛠 Core idea / reusable template
This pattern typically uses post-order recursion: compute values for left and right subtrees (height, sums, etc.) then combine them to compute the current node's value and potentially update a global answer.
Canonical height function:
int height(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(height(root.left), height(root.right));
}
Important template notes:
- Use post-order: left → right → combine.
- Use a helper method when you need to compute height and an extra global metric (diameter, max-sum, etc.).
- For early exits or detection of invalid states, use sentinel values (e.g., return -1 to indicate "unbalanced").
✅ Problems covered in this blog
- Maximum Depth of Binary Tree (LC 104)
- Balanced Binary Tree (LC 110) — check only (not rebalance)
- Diameter of Binary Tree (LC 543)
- Maximum Path Sum (LC 124)
- Longest Univalue Path (LC 687)
We'll provide brief explanation + production-ready Java code for each.
Single
TreeNodeclass used across examples:
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
1) Maximum Depth of Binary Tree (LC 104)
Idea: height as above.
Code
public class MaxDepth {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// Example usage
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(new MaxDepth().maxDepth(root)); // 3
}
}
Complexity: O(N) time, O(H) recursion stack.
Interview tip: simplest form of the pattern — use it as a building block.
2) Balanced Binary Tree (LC 110) — Check only
Definition: For every node, heights of left and right subtrees differ by ≤ 1.
Idea: Return height if subtree is balanced; return -1 if unbalanced. This avoids repeated height calculations.
Code
public class BalancedBinaryTree {
private int checkHeight(TreeNode root) {
if (root == null) return 0;
int left = checkHeight(root.left);
if (left == -1) return -1;
int right = checkHeight(root.right);
if (right == -1) return -1;
if (Math.abs(left - right) > 1) return -1;
return 1 + Math.max(left, right);
}
public boolean isBalanced(TreeNode root) {
return checkHeight(root) != -1;
}
// Example usage
public static void main(String[] args) {
BalancedBinaryTree bbt = new BalancedBinaryTree();
TreeNode root1 = new TreeNode(10);
root1.left = new TreeNode(5);
root1.right = new TreeNode(20);
System.out.println(bbt.isBalanced(root1)); // true
TreeNode root2 = new TreeNode(1);
root2.right = new TreeNode(2);
root2.right.right = new TreeNode(3);
System.out.println(bbt.isBalanced(root2)); // false
}
}
Complexity: O(N) time, O(H) space.
Interview tip: Explain early termination with -1 — this is crucial for O(N) performance.
3) Diameter of Binary Tree (LC 543)
Definition: diameter = number of nodes on the longest path between two nodes (some definitions use edges; here we return node count or convert to edges as needed).
Idea: For each node, potential diameter through it = leftHeight + rightHeight + 1 (nodes). Keep global max while computing heights.
Code (returns number of nodes on longest path)
public class DiameterOfBinaryTree {
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDiameter = 0;
height(root);
return maxDiameter; // number of nodes on the longest path
}
private int height(TreeNode node) {
if (node == null) return 0;
int left = height(node.left);
int right = height(node.right);
// diameter passing through this node = left + right + 1
maxDiameter = Math.max(maxDiameter, left + right + 1);
return 1 + Math.max(left, right);
}
// If problem expects number of edges, return maxDiameter - 1
}
Complexity: O(N) time, O(H) stack.
Variation: Many problems want diameter as number of edges — subtract 1.
Interview tip: Explain nodes vs edges clearly; interviewer may check which interpretation you used.
4) Maximum Path Sum (LC 124)
Definition: Maximum sum of values along any path in the tree. A path can start and end at any nodes but must be continuous (parent-child links).
Idea: For each node we compute:
-
maxPathDown: maximum path sum starting at node going down to either left or right (or 0 if negative). - Update global
maxSumwithleftMax + node.val + rightMax(path that passes through node).
Code
public class MaximumPathSum {
private int maxSum;
public int maxPathSum(TreeNode root) {
maxSum = Integer.MIN_VALUE;
maxGain(root);
return maxSum;
}
// returns max path sum starting from node and going down (one branch)
private int maxGain(TreeNode node) {
if (node == null) return 0;
// only take positive contributions
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// price of path that passes through this node
int priceNewpath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, priceNewpath);
// for recursion: return max gain if continuing the same path upwards
return node.val + Math.max(leftGain, rightGain);
}
// Example usage
public static void main(String[] args) {
/*
-10
/ \
9 20
/ \
15 7
max path = 15 + 20 + 7 = 42
*/
TreeNode root = new TreeNode(-10);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(new MaximumPathSum().maxPathSum(root)); // 42
}
}
Complexity: O(N) time, O(H) stack.
Interview tip: Emphasize why we Math.max(..., 0) — to drop negative contributions.
5) Longest Univalue Path (LC 687)
Definition: Longest path (number of edges) where every node on the path has the same value. Path can pass through parent connecting two child paths.
Idea: For each node, compute longest chain of same-value nodes down left and right, then combine for candidate that passes through the node. Track global max (in edges).
Code
public class LongestUnivaluePath {
private int maxLen = 0; // store edges count
public int longestUnivaluePath(TreeNode root) {
maxLen = 0;
dfs(root);
return maxLen;
}
// returns longest chain length (in edges) starting from node going down
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left);
int right = dfs(node.right);
int leftPath = 0, rightPath = 0;
if (node.left != null && node.left.val == node.val) {
leftPath = left + 1;
}
if (node.right != null && node.right.val == node.val) {
rightPath = right + 1;
}
// path through node = leftPath + rightPath (edges)
maxLen = Math.max(maxLen, leftPath + rightPath);
// return longest single-branch path to parent
return Math.max(leftPath, rightPath);
}
// Example usage
public static void main(String[] args) {
// tree: 5
// / \
// 4 5
// / \ \
// 1 1 5
TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(1);
root.right.right = new TreeNode(5);
System.out.println(new LongestUnivaluePath().longestUnivaluePath(root)); // 2 (two edges of 5-5-5)
}
}
Complexity: O(N) time, O(H) stack.
Interview tip: Track values carefully and remember the result is usually edges (not nodes). Always confirm expected unit.
🚀 Advanced variations & interview twists
- Return edges vs nodes: Many problems want edges count; clarify and convert accordingly.
-
Negative values (Max Path Sum): Handle by allowing global min initial value
Integer.MIN_VALUEand dropping negative gains upward. - K-ary trees: Same ideas extend — combine heights of multiple children.
- Path constraints: e.g., path length must be ≤ K — adapt DP to track top-K chain lengths.
- Balance with reconstruction: sometimes interviewer asks to rebalance after checking — use inorder → build balanced BST.
✅ Pattern checklist (quick recall)
When you see a tree problem, run through this mental checklist:
- Does it ask about longest/shortest path / height / balanced? → Height pattern.
- Will combining left & right results give answer for current node? → Use post-order.
- Do you need a global answer? → Use a class-level variable and update when combining.
- Is early termination possible (like unbalanced detection)? → Use sentinel returns (e.g., -1).
- Are negative contributions harmful? → Use
Math.max(value, 0)to prune negatives.
🧪 Practice problems (progression)
Start simple, then progress:
- Max Depth of Binary Tree — implement + explain recursion cost.
- Min Depth — BFS variation.
- Balanced Binary Tree — early termination trick.
- Diameter of Binary Tree — nodes vs edges.
- Maximum Path Sum — negative values testcases.
- Longest Univalue Path — edge vs node counting.
📌 Final notes (best practices)
- Always articulate whether you return height = #nodes or height = #edges (consistency).
- Use post-order to avoid recomputation of subtrees.
- Use early return (like -1) to optimize and avoid extra work.
- When writing code in interviews, quickly sketch a short example (3–5 nodes) and walk through recursion to show correctness.
Top comments (0)