Hierarchical data. Recursive DFS and level-order BFS are the two traversals you need.

Trees

What is a tree?

A tree is a connected, acyclic graph where each node has at most one parent and zero or more children. In interviews, "tree" almost always means binary tree - each node has at most two children named left and right:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

A Binary Search Tree (BST) adds an ordering property: every node in the left subtree is strictly smaller than the current node, and every node in the right subtree is strictly larger. This holds recursively at every level, which makes search O(log n) on a balanced tree - each comparison eliminates half the remaining candidates.

The core trade-off: trees give hierarchical structure and O(log n) search/insert on a balanced BST, but random access by index is O(n) and balance is not guaranteed. A BST built by inserting already-sorted keys degenerates into a linked list (O(n) everything). Most binary tree interview problems do not require the BST property - they just need traversal. Always distinguish whether the BST ordering is in play before choosing your approach.

Core operations

Operation	Balanced BST	Unbalanced / General Tree	Notes
Search	O(log n)	O(n)	BST property enables halving at each level
Insert	O(log n)	O(n)	Must find correct position without violating order
Delete	O(log n)	O(n)	Three cases: leaf, one child, two children
Min / Max	O(log n)	O(n)	Leftmost / rightmost node
In-order traversal	O(n)	O(n)	Visits all nodes in sorted order for a BST
Height	O(n)	O(n)	Must visit every node to find the deepest path

Key patterns

Recursive DFS traversal

Walk the tree by recursing into each child, processing the current node before, between, or after those two calls.

When to use - the answer for a node depends on its subtrees: a height, a path sum, a yes/no property, or a rebuilt copy. The tree's own recursive shape hands you the structure for free, so you skip writing an explicit stack and managing it by hand.

How it works - the function solves the whole problem for one node by first solving it for root.left, then for root.right, then combining the two answers. The base case is root is None, which returns the identity value (0 for height, True for a property, None for a miss). Where you place the node's own work picks the ordering: preorder (node first) copies structure, inorder (node in the middle) visits a BST in sorted order, postorder (node last) lets the parent read both children's results. Each node is visited once, so the pass is O(n) time; the call stack goes O(h) deep, which is O(log n) when balanced and O(n) for a degenerate tree.

Example: one tree, three orders. In 1, 2, 3, 4, 5, null, 6 node 2's children are 4 and 5 and node 3 has only a right child, 6. Preorder appends the node on arrival and yields 1, 2, 4, 5, 3, 6; postorder appends on the way out and yields 4, 5, 2, 6, 3, 1. Inorder appends after the left subtree returns, so it yields 4, 2, 5, 1, 3, 6 - the visualizer below runs all three on the same tree.

VisualizationVisit every node (3 orders)

0/18

order

call stack

dfs(1)

output

Visit 1.

▶def dfs(node, order, out):    if not node:        return    if order == 0: out.append(node.val)   # preorder    dfs(node.left, order, out)    if order == 1: out.append(node.val)   # inorder    dfs(node.right, order, out)    if order == 2: out.append(node.val)   # postorder    return out

Note

Postorder is the go-to for returning a value based on children - height, diameter, max path sum, and balanced-check all compute a value per node after knowing both children's values. Preorder and inorder cannot do this because the children have not been resolved yet.

Level-order BFS traversal

Visit the tree one depth at a time, finishing every node on a level before touching the next.

When to use - the problem is phrased by level: minimum depth, the right-side view, a zigzag order, or anything that needs nodes grouped by how far they sit from the root. DFS reaches every node too, but it dives deep first and loses the layer boundaries, so you'd have to reconstruct them afterward.

How it works - keep a deque, enqueue the root, and loop while it holds anything. At the top of each pass, snapshot len(queue) - that count is exactly the number of nodes on the current level. Dequeue precisely that many, process each, and enqueue its non-null children behind them. The snapshot is what draws the line between levels: the children you add belong to the next level, and capturing the size first keeps them out of the current one. Every node is enqueued and dequeued once, so it runs in O(n) time, with O(w) space for the widest level.

Example: print levels. In 8, 4, 11, null, null, 1, 6 node 11's children are 1 and 6, so the queue starts with 8, then holds 4 and 11, then 1 and 6. The snapshot takes 2, both are dequeued and appended to one level, and 1 and 6 land in the queue behind them. The result groups as [8], [4, 11], [1, 6] - the visualizer below shows the queue at each level.

VisualizationBinary Tree Level Order Traversal

0/15

queue

result

Enqueue root 8.

from collections import deque def level_order(root):    if not root:        return []▶    result, queue = [], deque([root])    while queue:        level = []        for _ in range(len(queue)):            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

Note

Snapshot len(queue) before the inner loop - the queue grows as you enqueue children inside the loop. Without capturing the level size first, you process children of the current level as part of the current level.

When to reach for a tree

The problem describes a hierarchical relationship (file systems, org charts, nested structures).
You need sorted operations with fast insert and delete - a balanced BST supports both in O(log n).
The problem gives you a binary tree and asks about paths, depths, or subtree properties - recursive DFS.
You need to process nodes level by level (minimum depth, right-side view, zigzag) - BFS with a queue.
The problem involves expression parsing or evaluation - expression trees with postorder traversal.
You need the k-th smallest or largest in a dynamic set - BST inorder yields sorted order.