DSA Tutorial
🔍
Binary Tree Operations
The Core Pattern: Postorder Bottom-Up
Most binary tree operations follow the same structural pattern: compute something for the left subtree, compute something for the right subtree, combine the results at the current node.
This is the postorder bottom-up pattern:
function solve(node):
if node is null: return BASE_VALUE
left_result = solve(node.left) ← 1. Get left answer
right_result = solve(node.right) ← 2. Get right answer
return combine(left_result, right_result, node) ← 3. Combine at current node
Examples of what changes per problem:
BASE_VALUE: 0 (height/count), true (symmetric), null (LCA)
combine: 1 + max(L, R) (height)
1 + L + R (count nodes)
L && R && match (symmetric)
if both non-null: current node (LCA)
Once you recognise this pattern, implementing any tree operation becomes a three-step exercise: what to return for null, what to return for a leaf, and how to combine child results.
Operation 1: Height of Binary Tree
Height = number of edges on the longest root-to-leaf path. Null node → height −1, or more commonly null → 0 with height of a single node = 1 (or equivalently, null → 0 and return value = max edge depth).
Tree: 1 Computing height bottom-up:
/ \
2 3 height(4) = 0 (leaf)
/ \ height(5) = 0 (leaf)
4 5 height(2) = 1 + max(0, 0) = 1
height(3) = 0 (leaf)
height(1) = 1 + max(1, 0) = 2
Height of tree = 2
Java
1public class TreeHeight {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Returns height of tree (number of edges to deepest leaf)
9 // null node returns -1 so that a leaf node has height 0
10 public static int height(TreeNode node) {
11 if (node == null) return -1; // Base case: null → -1
12 int leftH = height(node.left);
13 int rightH = height(node.right);
14 return 1 + Math.max(leftH, rightH); // Postorder combine
15 }
16
17 // Alternate convention: count nodes on path (null→0, leaf→1)
18 public static int heightNodes(TreeNode node) {
19 if (node == null) return 0;
20 return 1 + Math.max(heightNodes(node.left), heightNodes(node.right));
21 }
22
23 public static void main(String[] args) {
24 // 1
25 // / \
26 // 2 3
27 // / \
28 // 4 5
29 TreeNode root = new TreeNode(1);
30 root.left = new TreeNode(2); root.right = new TreeNode(3);
31 root.left.left = new TreeNode(4); root.left.right = new TreeNode(5);
32
33 System.out.println("Height (edges): " + height(root)); // 2
34 System.out.println("Height (nodes): " + heightNodes(root)); // 3
35
36 // Single node
37 TreeNode single = new TreeNode(1);
38 System.out.println("Single node height: " + height(single)); // 0
39
40 // Empty tree
41 System.out.println("Empty tree height: " + height(null)); // -1
42 }
43}Output:
Height (edges): 2
Height (nodes): 3
Single node height: 0
Empty tree height: -1
Operation 2: Diameter of Binary Tree
Diameter = number of edges in the longest path between any two nodes. The path may or may not pass through the root.
Tree: 1 Diameter = 4
/ \ (path: 5 → 2 → 1 → 3 → 6)
2 3
/ \ \
4 5 6
At each node, path length through that node = height(left) + height(right):
Node 4: 0 + 0 = 0 (leaf) diameter candidate = 0
Node 5: 0 + 0 = 0 (leaf) diameter candidate = 0
Node 2: 1 + 1 = 2 diameter candidate = 2 ← height(4or5)=0, so 0+0+1+1=2? No:
Actually: height(left of 2)=0, height(right of 2)=0
diameter through 2 = h(4) + h(5) = 0 + 0 + ? ...
Let's use height counting edges (null→-1, leaf→0):
h(4)=0, h(5)=0 → diameter through 2 = h(4)+1 + h(5)+1 = 2
h(3's right subtree): h(6)=0 → diameter through 3 = 0 + 1 = 1
diameter through 1 = (h(2)+1) + (h(3)+1) = (1+1) + (1+1) = 4
Global max across all nodes = 4 ✓
Java
1public class TreeDiameter {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 private static int maxDiameter = 0; // Tracks global maximum
9
10 // Returns height; updates maxDiameter as a side effect
11 private static int heightAndDiameter(TreeNode node) {
12 if (node == null) return -1;
13
14 int leftH = heightAndDiameter(node.left);
15 int rightH = heightAndDiameter(node.right);
16
17 // Path through this node: (leftH + 1) edges + (rightH + 1) edges
18 int pathThisNode = (leftH + 1) + (rightH + 1);
19 maxDiameter = Math.max(maxDiameter, pathThisNode);
20
21 return 1 + Math.max(leftH, rightH); // Return height
22 }
23
24 public static int diameter(TreeNode root) {
25 maxDiameter = 0;
26 heightAndDiameter(root);
27 return maxDiameter;
28 }
29
30 // Cleaner version using int[] to avoid static state
31 public static int diameterClean(TreeNode root) {
32 int[] maxD = {0};
33 computeHeight(root, maxD);
34 return maxD[0];
35 }
36
37 private static int computeHeight(TreeNode node, int[] maxD) {
38 if (node == null) return -1;
39 int lh = computeHeight(node.left, maxD);
40 int rh = computeHeight(node.right, maxD);
41 maxD[0] = Math.max(maxD[0], (lh + 1) + (rh + 1));
42 return 1 + Math.max(lh, rh);
43 }
44
45 public static void main(String[] args) {
46 // 1
47 // / \
48 // 2 3
49 // / \ \
50 // 4 5 6
51 TreeNode root = new TreeNode(1);
52 root.left = new TreeNode(2); root.right = new TreeNode(3);
53 root.left.left = new TreeNode(4); root.left.right = new TreeNode(5);
54 root.right.right = new TreeNode(6);
55
56 System.out.println("Diameter: " + diameter(root)); // 4
57 System.out.println("Diameter: " + diameterClean(root)); // 4
58
59 // Single node
60 System.out.println("Single: " + diameter(new TreeNode(1))); // 0
61 }
62}Output:
Diameter: 4
Diameter: 4
Single: 0
Operation 3: Balanced Binary Tree Check
A tree is balanced if for every node, |height(left) − height(right)| ≤ 1. Use the -1 sentinel to propagate imbalance in a single O(n) pass.
BALANCED: UNBALANCED:
1 1
/ \ \
2 3 ✓ 2
/ \ \
4 5 3 (diff = 2 at root) ✗
At node 1 (balanced tree):
height(2) = 1, height(3) = 0
|1 - 0| = 1 ≤ 1 ✓
At node 1 (unbalanced tree):
height(null) = -1, height(2) = 1
|(-1) - 1| = 2 > 1 ✗ → return -1 (imbalance signal)
Java
1public class BalancedTree {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 // Returns height if balanced, -1 if unbalanced
9 private static int checkBalance(TreeNode node) {
10 if (node == null) return -1; // null has height -1
11
12 int leftH = checkBalance(node.left);
13 if (leftH == -2) return -2; // Left subtree unbalanced — propagate
14
15 int rightH = checkBalance(node.right);
16 if (rightH == -2) return -2; // Right subtree unbalanced — propagate
17
18 if (Math.abs(leftH - rightH) > 1) return -2; // This node unbalanced
19
20 return 1 + Math.max(leftH, rightH); // Height of balanced subtree
21 }
22
23 public static boolean isBalanced(TreeNode root) {
24 return checkBalance(root) != -2;
25 }
26
27 public static void main(String[] args) {
28 // Balanced: 1
29 // / \
30 // 2 3
31 // / \
32 // 4 5
33 TreeNode balanced = new TreeNode(1);
34 balanced.left = new TreeNode(2); balanced.right = new TreeNode(3);
35 balanced.left.left = new TreeNode(4); balanced.left.right = new TreeNode(5);
36 System.out.println("Balanced: " + isBalanced(balanced)); // true
37
38 // Unbalanced: 1
39 // \
40 // 2
41 // \
42 // 3
43 TreeNode unbalanced = new TreeNode(1);
44 unbalanced.right = new TreeNode(2);
45 unbalanced.right.right = new TreeNode(3);
46 System.out.println("Unbalanced: " + isBalanced(unbalanced)); // false
47 }
48}Output:
Balanced: true
Unbalanced: false
Operation 4: Lowest Common Ancestor (LCA)
Find the deepest node that is an ancestor of both p and q.
Tree: 1
/ \
2 3
/ \ / \
4 5 6 7
LCA(4, 5) = 2 (4 and 5 both in left subtree of 2, but 2 is where they meet)
LCA(4, 6) = 1 (4 in left subtree, 6 in right subtree — split at root)
LCA(3, 7) = 3 (7 is in subtree of 3, and 3 itself is one of the targets)
ALGORITHM:
Postorder — search both subtrees.
At each node, return:
• the node itself if node == p or node == q
• left subtree result if only left side found something
• right subtree result if only right side found something
• the current node if BOTH sides found something (split point = LCA)
Java
1public class LCA {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
9 // Base case: null or found p or q
10 if (root == null || root == p || root == q) return root;
11
12 // Search both subtrees
13 TreeNode left = lowestCommonAncestor(root.left, p, q);
14 TreeNode right = lowestCommonAncestor(root.right, p, q);
15
16 // Both sides returned non-null → p and q are in different subtrees
17 // → current node is the LCA
18 if (left != null && right != null) return root;
19
20 // Only one side returned non-null → LCA is in that side
21 return left != null ? left : right;
22 }
23
24 public static void main(String[] args) {
25 // 1
26 // / \
27 // 2 3
28 // / \ / \
29 // 4 5 6 7
30 TreeNode root = new TreeNode(1);
31 root.left = new TreeNode(2); root.right = new TreeNode(3);
32 root.left.left = new TreeNode(4); root.left.right = new TreeNode(5);
33 root.right.left = new TreeNode(6); root.right.right = new TreeNode(7);
34
35 TreeNode n4 = root.left.left; // 4
36 TreeNode n5 = root.left.right; // 5
37 TreeNode n6 = root.right.left; // 6
38 TreeNode n3 = root.right; // 3
39
40 System.out.println("LCA(4,5): " + lowestCommonAncestor(root, n4, n5).val); // 2
41 System.out.println("LCA(4,6): " + lowestCommonAncestor(root, n4, n6).val); // 1
42 System.out.println("LCA(3,7): " + lowestCommonAncestor(root, n3, root.right.right).val); // 3
43 }
44}Output:
LCA(4,5): 2
LCA(4,6): 1
LCA(3,7): 3
Operation 5: Path Sum
Check whether any root-to-leaf path has a sum equal to the target.
Tree: 5 Target: 22
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Path 5→4→11→2 = 22 ← Found! ✓
Path 5→4→11→7 = 27
Path 5→8→13 = 26
Path 5→8→4→1 = 18
Algorithm: subtract node.val at each step.
At leaf: check if remaining == node.val (or remaining - node.val == 0).
Java
1public class PathSum {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 public static boolean hasPathSum(TreeNode root, int target) {
9 if (root == null) return false; // Empty tree — no path
10
11 // At a leaf: check if this node's value equals the remaining target
12 if (root.left == null && root.right == null) {
13 return root.val == target;
14 }
15
16 // Recurse — subtract current node's value from target
17 int remaining = target - root.val;
18 return hasPathSum(root.left, remaining) ||
19 hasPathSum(root.right, remaining);
20 }
21
22 public static void main(String[] args) {
23 // 5
24 // / \
25 // 4 8
26 // / / \
27 // 11 13 4
28 // / \ \
29 // 7 2 1
30 TreeNode root = new TreeNode(5);
31 root.left = new TreeNode(4); root.right = new TreeNode(8);
32 root.left.left = new TreeNode(11);
33 root.right.left = new TreeNode(13); root.right.right = new TreeNode(4);
34 root.left.left.left = new TreeNode(7);
35 root.left.left.right = new TreeNode(2);
36 root.right.right.right = new TreeNode(1);
37
38 System.out.println(hasPathSum(root, 22)); // true (5+4+11+2)
39 System.out.println(hasPathSum(root, 27)); // true (5+4+11+7)
40 System.out.println(hasPathSum(root, 18)); // true (5+8+4+1)
41 System.out.println(hasPathSum(root, 26)); // true (5+8+13)
42 System.out.println(hasPathSum(root, 100)); // false
43 }
44}Output:
true (5→4→11→2 = 22)
true (5→4→11→7 = 27)
true (5→8→4→1 = 18)
true (5→8→13 = 26)
false
Operation 6: Symmetric Tree
Check whether a binary tree is a mirror image of itself.
SYMMETRIC: NOT SYMMETRIC:
1 1
/ \ / \
2 2 ✓ 2 2
/ \ / \ \ \
3 4 4 3 3 3 ✗
(left has right child 3,
right has right child 3 — not mirrored)
isMirror(left, right):
null,null → true
null,non → false
non,null → false
else → left.val == right.val
AND isMirror(left.left, right.right) ← outer pair
AND isMirror(left.right, right.left) ← inner pair
Java
1public class SymmetricTree {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 private static boolean isMirror(TreeNode left, TreeNode right) {
9 if (left == null && right == null) return true; // Both null — symmetric
10 if (left == null || right == null) return false; // One null — asymmetric
11 return (left.val == right.val)
12 && isMirror(left.left, right.right) // Outer children match
13 && isMirror(left.right, right.left); // Inner children match
14 }
15
16 public static boolean isSymmetric(TreeNode root) {
17 if (root == null) return true;
18 return isMirror(root.left, root.right);
19 }
20
21 public static void main(String[] args) {
22 // Symmetric: 1
23 // / \
24 // 2 2
25 // / \ / \
26 // 3 4 4 3
27 TreeNode sym = new TreeNode(1);
28 sym.left = new TreeNode(2); sym.right = new TreeNode(2);
29 sym.left.left = new TreeNode(3); sym.left.right = new TreeNode(4);
30 sym.right.left = new TreeNode(4); sym.right.right = new TreeNode(3);
31 System.out.println("Symmetric: " + isSymmetric(sym)); // true
32
33 // Not symmetric: right subtree has wrong structure
34 TreeNode asym = new TreeNode(1);
35 asym.left = new TreeNode(2); asym.right = new TreeNode(2);
36 asym.left.right = new TreeNode(3); asym.right.right = new TreeNode(3);
37 System.out.println("Asymmetric: " + isSymmetric(asym)); // false
38 }
39}Output:
Symmetric: true
Asymmetric: false
Operation 7: Invert Binary Tree
Mirror the tree — swap left and right children at every node.
BEFORE: AFTER:
4 4
/ \ / \
2 7 → 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1
Java
1public class InvertTree {
2
3 static class TreeNode {
4 int val; TreeNode left, right;
5 TreeNode(int v) { val = v; }
6 }
7
8 public static TreeNode invertTree(TreeNode root) {
9 if (root == null) return null;
10
11 // Swap left and right children
12 TreeNode temp = root.left;
13 root.left = root.right;
14 root.right = temp;
15
16 // Recurse into both children
17 invertTree(root.left);
18 invertTree(root.right);
19
20 return root;
21 }
22
23 static void inorder(TreeNode n, java.util.List<Integer> r) {
24 if (n==null) return; inorder(n.left,r); r.add(n.val); inorder(n.right,r);
25 }
26
27 public static void main(String[] args) {
28 TreeNode root = new TreeNode(4);
29 root.left = new TreeNode(2); root.right = new TreeNode(7);
30 root.left.left = new TreeNode(1); root.left.right = new TreeNode(3);
31 root.right.left = new TreeNode(6); root.right.right = new TreeNode(9);
32
33 java.util.List<Integer> before = new java.util.ArrayList<>();
34 inorder(root, before);
35 System.out.println("Before inorder: " + before); // [1,2,3,4,6,7,9]
36
37 invertTree(root);
38
39 java.util.List<Integer> after = new java.util.ArrayList<>();
40 inorder(root, after);
41 System.out.println("After inorder: " + after); // [9,7,6,4,3,2,1]
42 }
43}Output:
Before inorder: [1, 2, 3, 4, 6, 7, 9]
After inorder: [9, 7, 6, 4, 3, 2, 1]
Operation Pattern Summary
OPERATION TRAVERSAL RETURN VALUE GLOBAL STATE? ──────────────────────────────────────────────────────────────────── Height Postorder height (int) No Diameter Postorder height (int) Yes — maxDiameter Count nodes Postorder count (int) No Balanced check Postorder height or -2 No (-2 = sentinel) LCA Postorder TreeNode or null No Path sum Preorder boolean No Symmetric Both subs boolean No Invert Preorder void (in-place) No COMBINING RULES per operation: Height: 1 + max(L, R) Count: 1 + L + R Balanced: if |L-R|>1: return -2; else 1+max(L,R) Diameter: update global with (L+1)+(R+1); return 1+max(L,R) LCA: if both: return node; else: return non-null side PathSum: at leaf: val==target; else: L || R Symmetric: val match && mirror(L.left,R.right) && mirror(L.right,R.left) Invert: swap(L,R) then recurse
Complexity Summary
| Operation | Time | Space | Pattern |
|---|---|---|---|
| Height | O(n) | O(h) | Postorder |
| Diameter | O(n) | O(h) | Postorder + global |
| Count nodes | O(n) | O(h) | Postorder |
| Balanced check | O(n) | O(h) | Postorder (-1 sentinel) |
| LCA | O(n) | O(h) | Postorder |
| Path sum | O(n) | O(h) | Preorder |
| Symmetric | O(n) | O(h) | Pairwise DFS |
| Invert | O(n) | O(h) | Preorder |
All O(n) time — every node visited once. All O(h) space for the call stack: O(log n) balanced, O(n) skewed.
Common Mistakes
Diameter: computing at root only. The diameter may pass through any node, not just the root. Always update a global maximum at every node during the height computation. Computing height(left) + height(right) only at the root gives the wrong answer for trees where the longest path is entirely within a subtree.
Path sum: returning true when target becomes 0 at a null node. If you check if root is None and target == 0: return True, a path that stops at an internal node with a single null child will incorrectly return true. The leaf check must be explicit: if not root.left and not root.right: return root.val == target.
Balanced: checking only the root. A tree is balanced only if every node is balanced. Returning abs(height(left) - height(right)) <= 1 at the root alone misses imbalances in subtrees. The sentinel (-1 or -2) approach correctly propagates imbalance from any node upward.
Symmetric: checking left.left vs right.left (same side). The mirror check crosses sides: isMirror(left.left, right.right) and isMirror(left.right, right.left). A common mistake is checking isMirror(left.left, right.left) — same side — which tests structural equality rather than mirror symmetry.
LCA: not handling the case where p or q is an ancestor of the other. When checking if root == p or root == q: return root, this correctly handles the case where one of the targets is an ancestor of the other. The ancestor node is returned, and since the other target is in its subtree, the subtree search returns null — the ancestor becomes the LCA.
Summary
Binary tree operations follow the postorder bottom-up pattern: get results from left and right subtrees, then combine them at the current node.
The seven core operations and their combining rules:
Height: null→-1; return 1 + max(L, R) Diameter: update global with (L+1)+(R+1); return 1+max(L,R) Balanced: if |L-R|>1 return -2; else return 1+max(L,R) LCA: null/p/q→return self; if both L,R non-null→return node PathSum: at leaf return val==target; else L || R on (target-val) Symmetric: null,null→T; one null→F; val match AND cross-mirror of both sides Invert: swap(L,R) then recurse; return root
All operations are O(n) time and O(h) space. The key design decisions:
- ›Use -1 sentinel for balanced check to avoid two passes
- ›Use global variable (or closure) for diameter
- ›Check at leaf (not null) for path sum
- ›Cross the sides (
left.left ↔ right.right) for symmetric check
In the next topic you will explore Binary Tree Hard Problems — maximum path sum, serialize/deserialize, construct from traversals, and more advanced patterns.
Suggested Quiz
Computing height of a binary tree uses which traversal order and why?
1/6