What a Tree Is
A tree is a hierarchical data structure where each node has a value and zero or more child nodes, with exactly one path between any two nodes and no cycles. The most common interview variant is the binary tree, where each node has at most two children (left and right). A Binary Search Tree (BST) adds the constraint that all values in the left subtree are smaller than the node's value, and all values in the right subtree are larger.
The Three DFS Traversals
All three traversals visit every node exactly once — they differ only in when they process the current node relative to its children.
4
/ \
2 6
/ \ / \
1 3 5 7
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder(root): # Left → Node → Right → [1,2,3,4,5,6,7] (sorted for BST)
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
def preorder(root): # Node → Left → Right → [4,2,1,3,6,5,7] (good for copying/serializing)
if not root: return []
return [root.val] + preorder(root.left) + preorder(root.right)
def postorder(root): # Left → Right → Node → [1,3,2,5,7,6,4] (good for deletion/evaluation)
if not root: return []
return postorder(root.left) + postorder(root.right) + [root.val]
BFS (Level-Order Traversal): Uses a queue instead of recursion. Visits all nodes at depth d before any node at depth d+1. Essential for "find the shortest path" or "level-by-level" problems.
from collections import deque
def level_order(root):
if not root: return []
result, queue = [], deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
Common Tree Interview Patterns
| Problem Type | Technique |
|---|---|
| Validate BST | Inorder traversal should be strictly increasing |
| Max depth / height | Postorder DFS: 1 + max(left_depth, right_depth) |
| Lowest Common Ancestor | DFS returning the node when both targets found in subtrees |
| Serialize/Deserialize | Preorder DFS with null markers |
| Level-by-level output | BFS with queue |