Trees - Introduction
A tree is a hierarchical data structure where each node has a value and zero or more child nodes. The most common form in interviews is the Binary Tree: each node has at most two children (left and right). Understanding tree traversals and the Binary Search Tree (BST) property is fundamental to solving most tree problems.
Contents
Key Terminology
- 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.
TreeNode Definition
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;
}
}BST Property
A Binary Search Tree (BST) maintains the invariant: for every node n< n.val> 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: Inorder, Preorder, Postorder
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 (BFS)
Level-order traversal visits nodes level by level using a Queue
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;
}queue.size()Complexity
- 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.