Contents
- Key Terminology
- TreeNode Definition
- BST Property
- DFS Traversals — Inorder, Preorder, Postorder
- Level-Order Traversal (BFS)
- Complexity
- Root — the topmost node with no parent.
- Leaf — a node with no children.
- Height — longest path from root to a leaf (edges). A single-node tree has height 0.
- Depth — distance from root to a given node.
- Balanced tree — the height difference between left and right subtrees of every node is at most 1 (e.g., AVL, Red-Black trees).
- Complete binary tree — all levels fully filled except possibly the last, filled from left to right.
- Full binary tree — every node has 0 or 2 children.
- Perfect binary tree — all internal nodes have 2 children and all leaves are at the same level.
LeetCode uses this standard definition for binary tree nodes:
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;
}
}
A Binary Search Tree (BST) maintains the invariant: for every node n,
all values in the left subtree are < n.val and all values in the
right subtree are > n.val.
- Search, insert, and delete: O(h) where h is height.
- Balanced BST: O(log n). Degenerate (sorted input): O(n).
- Inorder traversal of a BST produces sorted output.
DFS traversals differ only in when the current node is processed relative to its subtrees:
- Inorder (Left → Node → Right) — gives sorted output for BST.
- Preorder (Node → Left → Right) — useful for serializing/copying a tree.
- Postorder (Left → Right → Node) — useful when you need to process children before parent (e.g., deleting a tree).
// Recursive DFS — all three traversals
void inorder(TreeNode root, List<Integer> result) {
if (root == null) return;
inorder(root.left, result); // left
result.add(root.val); // node
inorder(root.right, result); // right
}
void preorder(TreeNode root, List<Integer> result) {
if (root == null) return;
result.add(root.val); // node
preorder(root.left, result); // left
preorder(root.right, result); // right
}
void postorder(TreeNode root, List<Integer> result) {
if (root == null) return;
postorder(root.left, result); // left
postorder(root.right, result); // right
result.add(root.val); // node
}
Iterative inorder using an explicit stack:
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) { // go as far left as possible
stack.push(curr);
curr = curr.left;
}
curr = stack.pop(); // process node
result.add(curr.val);
curr = curr.right; // move to right subtree
}
return result;
}
Level-order traversal visits nodes level by level using a Queue.
This is the basis for most tree problems that ask for "level-by-level" results.
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size(); // number of nodes at current level
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
The key insight: snapshot queue.size() at the start of each outer loop iteration. This tells you exactly how many nodes belong to the current level before you add the next level's nodes.
- Time: O(n) — every traversal visits each node exactly once.
- Space: O(h) — DFS recursion stack depth equals tree height h. Worst case O(n) for skewed tree, O(log n) for balanced.
- Space: O(n) — BFS queue can hold up to n/2 nodes at the widest level.