Trees

Binary Tree Fundamentals

A hierarchical structure where each node has at most two children — left and right. The conceptual foundation for BST, Heap, Trie, and every recursive divide-and-conquer algorithm on trees.

Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.
01
Section One · Foundation

What is Binary Tree?

8 3 10 1 6 9 14 root internal leaf leaf height = 2

Hierarchical data structures unlock algorithmic patterns that linear structures cannot express — trees encode parent-child relationships naturally, enabling divide-and-conquer solutions that split problems in half at every level and achieve O(log n) performance where arrays and lists require O(n). Each node in a binary tree holds a value and references to at most two children, called left and right, with one designated root node at the top and no cycles — this constraint enables a recursive definition where every binary tree is either empty or a node with a left binary tree and a right binary tree. Every binary tree algorithm follows one universal pattern: do something at the current node, recurse into the left subtree, recurse into the right subtree — the only variation is the order of these three steps, which produces the four traversal orders (preorder, inorder, postorder, level-order). The recursive structure means any operation you can perform on the whole tree works identically on any subtree, making trees the natural home for recursive thinking. Java's TreeMap and TreeSet use red-black trees internally, expression parsers build abstract syntax trees, and XML/JSON parsers represent hierarchical documents as trees — understanding binary trees is prerequisite to understanding half of computer science.

Analogy: A corporate org chart where every manager has at most two direct reports. The CEO is the root — no one manages the CEO. Every employee either has zero, one, or two direct reports. To find information about any employee, you start at the CEO and follow the reporting structure down — each decision point either sends you left or right, cutting the remaining organisation in half at each step. That halving at each level is why balanced trees are so fast.
02
Section Two · Mental Model

How It Thinks

Each node has at most two children
▶
Every problem splits into two independent subproblems — divide and conquer is structurally enforced
Tree has no cycles — each node has exactly one parent
▶
Recursion terminates naturally — null is the base case, every path to null is finite
Height h determines path length from root to leaf
▶
Balanced tree: h = O(log n) — operations proportional to height cost O(log n); unbalanced: h = O(n), same as a linked list
Every subtree is itself a valid binary tree
▶
Recursive algorithms apply identically to the whole tree and any subtree — no special cases for subtrees
Three positions relative to children: before, between, after
▶
Three traversal orders — preorder, inorder, postorder — each revealing different structural information
No index, no hash — only parent/child pointers
▶
Search is O(n) without an ordering invariant — the BST ordering constraint is what makes search O(log n)
03
Section Three · Terminology

Tree Terminology

Binary tree problems use a precise vocabulary that appears in every problem statement, every solution discussion, and every interview question — knowing these terms cold prevents misunderstanding during problem analysis. The most commonly confused pairs are height vs depth (height measures from node down to farthest leaf; depth measures from root down to node) and full vs complete vs perfect (three distinct structural properties often incorrectly used interchangeably).

Tree Anatomy — terminology reference
A B C D E F G H I depth=0 depth=1 depth=2 depth=3 Level 0 Level 1 Level 2 Level 3 h=3 h=2 h=1 h=1 h=0 h=0 h=0 h=0 h=0 root subtree rooted at B siblings: D & E leaf leaf leaf
Terminology Reference
Term Definition Example in diagram
Root The topmost node — no parent Node A
Leaf Node with no children H, I, E, F, G
Internal node Node with at least one child A, B, C, D
Parent The node directly above A is parent of B and C
Child Direct descendant of a node B and C are children of A
Sibling Nodes sharing the same parent D and E are siblings
Ancestor Any node on path from root to node A, B are ancestors of D
Descendant Any node reachable going down D, H, I are descendants of B
Edge Connection between parent and child A—B is an edge
Path Sequence of edges between two nodes A→B→D→H
Depth Distance from root to a node depth(D) = 2
Height of node Max edges to a leaf in its subtree height(B) = 2
Height of tree Height of the root node height(A) = 3
Level Set of all nodes at same depth Level 2 = {D, E, F, G}
Subtree A node and all its descendants Subtree rooted at B
Degree Number of children of a node degree(B) = 2, degree(H) = 0
Height vs depth — the most confused tree terms:
  • Depth of a node counts edges from the root DOWN to that node — the root has depth 0.
  • Height of a node counts edges from that node DOWN to the farthest leaf — a leaf has height 0.
  • The height of a tree equals the height of its root.
  • These two measures run in opposite directions on the same tree, which is why they are so often confused.
04
Section Four · Tree Types

Tree Types and Structural Properties

Five structural properties define the tree types that appear in interviews and algorithms — each is a constraint on the shape of the tree that enables specific operations or guarantees specific performance bounds. The most practically important are complete binary tree (enables array storage of heap) and balanced binary tree (guarantees O(log n) height for BST and AVL trees).

Five tree types — structural properties
FULL A B C D E Every node has 0 or 2 children COMPLETE A B C D E F All levels full except last; last filled left to right PERFECT A B C D E F G All leaves at same level, all internals have 2 children n = 2^(h+1) - 1 BALANCED A B C D E F |height(L) - height(R)| ≤ 1 for every node h(L)=1, h(R)=1 → |diff|=0 ✓ DEGENERATE A B C D Every node has exactly 1 child = linked list height = n-1
Comparison
Tree Type Every node Leaves Height Notes
Full 0 or 2 children Any level O(log n) to O(n) Used in expression trees
Complete Any Deepest level, left-packed O(log n) Heap structure
Perfect Exactly 2 (non-leaf) All same level Exactly log n Theoretical ideal
Balanced Any Any level O(log n) AVL, Red-Black trees
Degenerate Exactly 1 child One leaf O(n) Sorted-insert BST pathology
Complete binary tree enables O(1) array storage:
  • A complete binary tree can be stored in an array with no pointers — the root is at index 1, left child of node i is at 2i, right child at 2i+1, parent at i/2.
  • This is why heap (PriorityQueue) uses an array internally — the complete tree property guarantees no gaps, so the array has no wasted space.
05
Section Five · Traversals

Tree Traversals

Inorder Traversal (Left → Root → Right)
Visits the left subtree, then the current node, then the right subtree — produces sorted output on a BST.
Pseudocode
function inorder(node): if node is null: return inorder(node.left) // recurse left first visit(node) // process current node inorder(node.right) // recurse right last // O(n) — visits every node once
Inorder traversal — visit order numbered 1–7
8 3 10 1 6 9 14 4 2 6 1 3 5 7 Result: [1, 3, 6, 8, 9, 10, 14] — sorted order on a BST
Inorder = sorted output on a BST:
  • The inorder traversal of a BST always produces elements in ascending sorted order — this is provable from the BST invariant.
  • The kth smallest element in a BST is found by inorder traversal stopping at the kth visited node.
Preorder Traversal (Root → Left → Right)
Visits the current node first, then the left subtree, then the right subtree — used for tree copying and serialisation.
Pseudocode
function preorder(node): if node is null: return visit(node) // process current node FIRST preorder(node.left) // recurse left preorder(node.right) // recurse right // O(n)
Preorder traversal — visit order numbered 1–7
8 3 10 1 6 9 14 1 2 5 3 4 6 7 Result: [8, 3, 1, 6, 10, 9, 14] — root always first
Preorder = tree serialisation format:
  • If you serialise a binary tree by writing nodes in preorder, you can reconstruct the original tree from the serialised form because the root always appears first.
  • This is the basis of LeetCode 297 (Serialize and Deserialize Binary Tree).
Postorder Traversal (Left → Right → Root)
Visits both subtrees completely before visiting the current node — used when a node's value depends on its children.
Pseudocode
function postorder(node): if node is null: return postorder(node.left) // recurse left postorder(node.right) // recurse right visit(node) // process current node LAST // O(n)
Postorder traversal — visit order numbered 1–7
8 3 10 1 6 9 14 7 3 6 1 2 4 5 Result: [1, 6, 3, 9, 14, 10, 8] — root always last
Postorder = process children before parent: Postorder is used when computing a node's value requires its children's values first — tree height (need subtree heights before computing node height), directory size, and expression tree evaluation.
Level-Order Traversal (BFS)
Visits all nodes at depth 0, then depth 1, then depth 2 — processes the tree level by level using a queue.
Pseudocode
function levelOrder(root): if root is null: return queue = new Queue enqueue(queue, root) while queue is not empty: node = dequeue(queue) visit(node) // O(1) per node if node.left is not null: enqueue(queue, node.left) if node.right is not null: enqueue(queue, node.right) // O(n) total
Level-order traversal — queue state at each step
8 3 10 1 6 9 14 Level 0 Level 1 Level 2 Queue State: Step 1: Dequeue 8 → [3, 10] Step 2: Dequeue 3 → [10, 1, 6] Step 3: Dequeue 10 → [1, 6, 9, 14] Step 4–7: Dequeue leaves... [ ] Visit order: 8, 3, 10, 1, 6, 9, 14 — level by level
Level-order = BFS = shortest path tree exploration:
  • Level-order traversal and BFS are the same algorithm — both use a queue and both process nodes by distance from the start.
  • When a problem asks for "minimum depth" or "level-by-level processing", level-order is the answer.
Traversal Comparison
Traversal Order Use Case Output on BST {8,3,10,1,6,9,14}
Inorder Left → Root → Right Sorted output, kth smallest 1, 3, 6, 8, 9, 10, 14
Preorder Root → Left → Right Serialisation, prefix expr 8, 3, 1, 6, 10, 9, 14
Postorder Left → Right → Root Height, size, deletion 1, 6, 3, 9, 14, 10, 8
Level-Order Level by level Min depth, level sums, BFS 8 | 3, 10 | 1, 6, 9, 14
Iterative Versions
Java — Iterative Inorder and Preorder
// Iterative Inorder — stack-based List<Integer> inorderIterative(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); result.add(curr.val); // visit curr = curr.right; // move right } return result; } // Iterative Preorder — simpler: push right then left List<Integer> preorderIterative(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); // visit before children if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } return result; }
Iterative inorder uses a two-phase loop — understand it:
  • The iterative inorder pattern (go left until null pushing to stack, then pop, visit, go right) simulates the call stack of the recursive version.
  • Trace through 3 nodes by hand once — it becomes intuitive.
06
Section Six · Operations

Core Operations

Height of Tree
Returns the number of edges on the longest path from the root to any leaf — the base case is null returning -1 (or 0 if counting nodes rather than edges).
Pseudocode
function height(node): if node is null: return -1 // -1 for edge-count definition leftHeight = height(node.left) rightHeight = height(node.right) return 1 + max(leftHeight, rightHeight) // O(n) — visits every node
Height computation — bottom-up with return values
returns 0 returns 0 returns 0 returns 1 A B C D E h = 2 h = 1 h = 0 h = 0 h = 0 Postorder: compute children heights before parent (h = 1 + max(left, right))
Height is a postorder computation:
  • Height requires knowing the heights of both subtrees before computing the current node's height — that is postorder: children first, then parent.
  • Any operation that aggregates information bottom-up (height, size, sum, balance check) is naturally postorder.
Count Nodes
Returns the total number of nodes in the tree — the base case is null returning 0, and every node contributes 1.
Pseudocode
function countNodes(node): if node is null: return 0 // base case — empty tree return 1 + countNodes(node.left) + countNodes(node.right) // O(n) — visits every node
Count, sum, and height all share the same skeleton:
  • countNodes = 1 + count(left) + count(right). sumValues = node.val + sum(left) + sum(right). height = 1 + max(h(left), h(right)).
  • These are the same postorder template with different combination functions.
Check if Balanced
Returns true if the absolute difference between the heights of the left and right subtrees is at most 1 for every node in the tree — O(n) when done in one pass.
Pseudocode
function isBalanced(node): return checkHeight(node) != -1 // -1 signals unbalanced function checkHeight(node): if node is null: return 0 leftH = checkHeight(node.left) if leftH == -1: return -1 // propagate unbalanced signal rightH = checkHeight(node.right) if rightH == -1: return -1 if |leftH - rightH| > 1: return -1 // this node is unbalanced return 1 + max(leftH, rightH) // O(n) — one pass
Naive O(n²) vs O(n) balance check:
  • The naive approach calls height() at every node — O(n) per node × O(n) nodes = O(n²).
  • The single-pass approach uses -1 as a sentinel value that propagates upward when any subtree is unbalanced, short-circuiting the rest of the traversal.
Lowest Common Ancestor (LCA)
Finds the deepest node that is an ancestor of both p and q — the meeting point when climbing from both nodes toward the root.
Pseudocode
function lca(node, p, q): if node is null: return null if node == p or node == q: return node // found one of the targets left = lca(node.left, p, q) right = lca(node.right, p, q) if left is not null and right is not null: return node // p and q are in different subtrees return left if left is not null else right // O(n)
LCA: if both subtrees return non-null, current node is the answer:
  • The insight is that if p and q are in different subtrees, the current node is their LCA — both recursive calls return non-null simultaneously only when they are on opposite sides.
  • If both are in the same subtree, only one call returns non-null and that result propagates upward.
Common Mistake: Forgetting the null base case at the top of every recursive tree function. Without if (node == null) return ..., the function throws NullPointerException when it reaches a leaf and tries to access node.left or node.right. Every recursive tree function must handle the null case first — it is not optional.
07
Section Seven · Recursion

Recursion on Trees — The Universal Pattern

Every binary tree algorithm — traversal, search, height, LCA, path sum, serialisation — is a variation of the same three-line recursive skeleton: handle the null case, process or recurse into the left subtree, process or recurse into the right subtree. The only decisions are: what order to do these three things (pre, in, or post), what information to pass down (top-down), and what information to return up (bottom-up). Internalising this template means that when you see a new tree problem, you are not inventing an algorithm — you are choosing values for three variables in a template you already know.

The Universal Tree Recursion Template
Java — The Template
// THE TEMPLATE — every binary tree problem fits this skeleton ReturnType solve(TreeNode node /* optional state passed down */) { // ① BASE CASE — always check null first if (node == null) return BASE_VALUE; // ② PREORDER WORK — do something BEFORE recursing // Use when: parent info needed by children // Example: path problems, serialisation, accumulating prefix doSomethingBefore(node); // ③ RECURSE INTO CHILDREN ReturnType leftResult = solve(node.left /* updated state */); ReturnType rightResult = solve(node.right /* updated state */); // ④ POSTORDER WORK — do something AFTER recursing // Use when: children results needed to compute current // Example: height, size, LCA, balance check return combine(node, leftResult, rightResult); } // ─── CONCRETE EXAMPLES filling the template ───────────────────── // Height: BASE=-1, combine = 1 + max(L, R) // Count: BASE=0, combine = 1 + L + R // Sum: BASE=0, combine = node.val + L + R // Max path: BASE=0, global max updated in combine // Balanced: BASE=0, combine = |L-R|>1 ? -1 : 1+max(L,R) // Inorder: no return, visit between left and right recurse
Top-Down (Preorder)

Pass information DOWN

The parent computes something and passes it to the children as a parameter. Children use the passed value, not their own subtree results, to make decisions.

  • Path sum check (pass remaining target down)
  • Max depth from root (pass current depth down)
  • Path encoding (pass current path string down)
  • BST validation (pass min/max bounds down)
Bottom-Up (Postorder)

Return information UP

Children compute something and return it to the parent. The parent combines the children's results to compute its own result. Information flows from leaves to root.

  • Tree height (children return heights)
  • Tree size (children return counts)
  • LCA (children return found nodes)
  • Balance check (children return heights or -1)
Recursion Strategy Decision
What does the current node need? needs info FROM parent needs results FROM children both Top-Down pass as parameter Bottom-Up recurse then combine Both pass down AND return up path sum, BST validation height, LCA, balance max path sum, diameter
Every tree problem in an interview maps to this template:
  • Before writing any code for a tree problem, identify: (1) what the function returns — single value, list, boolean, or void with side effects; (2) what the base case is for null; (3) whether you need top-down or bottom-up.
  • Once these three are decided, the code is structural.
08
Section Eight · Implementation

Build It Once

Build this from scratch once — it makes the mechanics concrete. In any real project or interview, the standard LeetCode TreeNode is already provided.

Java — Binary Tree core mechanics
// The LeetCode TreeNode is the standard interview definition. // Build tree operations using recursion — not iteration — first. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } } // Height — postorder bottom-up: O(n) int height(TreeNode node) { if (node == null) return -1; return 1 + Math.max(height(node.left), height(node.right)); } // Inorder — recursive, appends to result list: O(n) void inorder(TreeNode node, List<Integer> result) { if (node == null) return; inorder(node.left, result); result.add(node.val); // visit between children inorder(node.right, result); } // isBalanced — O(n) single pass with -1 sentinel boolean isBalanced(TreeNode root) { return checkHeight(root) != -1; } int checkHeight(TreeNode node) { if (node == null) return 0; int l = checkHeight(node.left); if (l == -1) return -1; // short-circuit int r = checkHeight(node.right); if (r == -1 || Math.abs(l - r) > 1) return -1; return 1 + Math.max(l, r); }
09
Section Nine · Java Reference

Use It In Java

IN JAVA — No Built-in Binary Tree
Use No built-in BinaryTree — build TreeNode from scratch. For sorted-tree operations: TreeMap<K,V> or TreeSet<E>
LeetCode Standard TreeNode — memorise this
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }
Need Use Why
Sorted key-value storage TreeMap<K,V> Red-black tree, O(log n) all ops
Sorted unique elements TreeSet<E> Red-black tree, O(log n) all ops
Priority ordering PriorityQueue<E> Binary min-heap (complete tree)
General binary tree Custom TreeNode No built-in equivalent
⚠ Gotcha: Java's TreeMap and TreeSet are balanced BSTs (red-black trees) but expose no node-level API — you cannot traverse the tree structure, access parent pointers, or perform tree rotations. For any problem requiring node-level tree manipulation (LCA, path sum, serialisation), build TreeNode from scratch.
Choose Use TreeMap/TreeSet when you need sorted collections with O(log n) operations. Use a custom TreeNode for any tree structure problem, algorithm implementation, or interview question involving tree manipulation directly.
10
Section Ten · Practice

Problems To Solve

Binary tree interview problems almost always require one of two approaches: DFS recursion using the universal postorder/preorder template (height, balance, LCA, path sum, serialisation), or BFS level-order traversal with a queue (minimum depth, level-by-level processing, connect next pointers). When you read a tree problem, ask two questions first: does the answer depend on processing children before the parent (postorder DFS), or does it require processing nodes level by level (BFS)? The answer determines your entire algorithm structure.

Difficulty Pattern Problem Key Insight
Easy dfs Maximum Depth of Binary Tree — LC 104 The height of a node is 1 + max(height(left), height(right)) — base case is null returns 0. One line of recursion.
Easy dfs Invert Binary Tree — LC 226 Swap left and right at the current node, then recurse into both children — postorder or preorder both work.
Easy dfs Symmetric Tree — LC 101 Two pointers that mirror each other: left.left vs right.right and left.right vs right.left must match at every level.
Medium bfs Binary Tree Level Order Traversal — LC 102 BFS with a size snapshot — record queue.size() at the start of each level to know when one level ends and the next begins.
Medium dfs Lowest Common Ancestor of a Binary Tree — LC 236 If both p and q are in different subtrees of a node, that node is the LCA. If one equals the current node, the current node is the LCA.
Hard dfs Binary Tree Maximum Path Sum — LC 124 At each node, the best path through it is node.val + max(0, left gain) + max(0, right gain). Track global max while returning only the best single-branch gain upward.
Interview Pattern:
  • For 90% of binary tree problems, write the recursive function signature first, then the null base case, then decide: does the current node need information passed down from the parent (top-down), or does it need results returned from children (bottom-up)?
  • The code follows from this decision.

→ See all Binary Tree problems with full solutions