Trees are the first non-linear data structure you will encounter, and they change how you think about algorithms. With arrays and linked lists, data flows in a single line - one element after another. Trees branch. Every node can lead to multiple paths, and this branching structure is what makes trees powerful for modeling hierarchies, decisions, and recursive decomposition.

Before you can traverse a tree, you need precise vocabulary. Sloppy terminology leads to sloppy thinking, and in interviews, that means bugs.

Core Terminology

A binary tree is a tree where each node has at most two children, called the left child and right child. Here are the terms you must know cold:

• Root: The topmost node. It has no parent. Every tree has exactly one root.
• Leaf: A node with no children. Leaves are where recursion hits its base case.
• Internal node: Any node that has at least one child - everything that is not a leaf.
• Parent: The node directly above a given node.
• Child: A node directly below a given node. In a binary tree, a node has at most two children.
• Sibling: Two nodes that share the same parent.
• Subtree: Any node together with all its descendants forms a subtree. The left subtree of a node is the tree rooted at its left child.
• Depth: The number of edges from the root to a node. The root has depth 0.
• Height: The number of edges on the longest path from a node down to a leaf. A leaf has height 0. The height of the tree is the height of the root.

Understanding the difference between depth and height trips up many people. Depth is measured downward from the root (how far is this node from the top?). Height is measured upward from the leaves (how far is this node from the bottom?).

The Node Structure

A binary tree node is remarkably simple - just three fields:

Compare this to a linked list node that stores val and next. A tree node stores val, left, and right. That one extra pointer is what transforms a linear chain into a branching structure.

To build a small tree manually:

In this tree, node 1 is the root, nodes 4, 5, and 3 are leaves, and node 2 is an internal node. The depth of node 5 is 2 (two edges from the root). The height of the tree is 2 (longest path from root to a leaf).

Binary Tree vs General Tree

A general tree allows any number of children per node. File systems are general trees - a directory can contain any number of subdirectories. A binary tree restricts each node to at most two children, which simplifies traversal algorithms and enables powerful divide-and-conquer strategies. Most interview problems focus on binary trees because the two-child constraint creates clean recursive structure: solve the left subtree, solve the right subtree, combine the results.

Types of Binary Trees

Three specific shapes come up repeatedly:

Full binary tree: Every node has either 0 or 2 children. No node has exactly one child. This means every internal node branches into exactly two paths.

Complete binary tree: Every level is completely filled except possibly the last, and the last level is filled from left to right. Binary heaps are stored as complete binary trees. The shape guarantee is what allows array-based storage - the parent of node at index i is at index (i-1)//2, and the children are at 2i+1 and 2i+2.

Perfect binary tree: Every internal node has exactly two children and all leaves are at the same depth. A perfect binary tree of height h has exactly 2^(h+1) - 1 nodes. These are rare in practice but useful for understanding the theoretical best case.

The key distinction: a perfect tree is both full and complete, but a full tree is not necessarily complete, and a complete tree is not necessarily full. Complete trees fill left-to-right on the last level, while full trees require every node to have exactly 0 or 2 children.

Height and Balance

The height of a binary tree determines the performance of almost every tree algorithm. A balanced binary tree has height O(log n), where n is the number of nodes. This happens when nodes are distributed roughly evenly between left and right subtrees. Searching, inserting, and traversing all benefit from logarithmic height.

A degenerate (or skewed) tree is the worst case - every node has only one child, forming a straight line. This is effectively a linked list, and the height becomes O(n). All the advantages of tree structure vanish.

1Balanced (height = 2):       Degenerate (height = 4):
2      1                        1
3     / \                        \
4    2   3                        2
5   / \   \                        \
6  4   5   6                        3
7                                    \
8                                     4
9                                      \
10                                       5

This is why self-balancing trees (AVL trees, red-black trees) exist - they enforce O(log n) height through rotations after insertions and deletions. You do not need to implement them in most interviews, but you need to know that balanced height is O(log n) and degenerate height is O(n), because this directly affects the time complexity of every recursive algorithm you write on trees.

Traversing a binary tree means visiting every node exactly once. Unlike a linked list where there is only one path (follow next), a binary tree branches at every node. You have to choose: do you process the current node before its children, between its children, or after its children? That choice gives you three distinct depth-first traversals, each with different applications.

Understanding why each order exists - not just memorizing the sequences - is what separates someone who can solve tree problems from someone who gets stuck.

The Three DFS Traversals

Every depth-first traversal visits three things at each node: the left subtree, the current node, and the right subtree. The only difference is when you process the current node:

• Inorder (Left, Root, Right): Process the left subtree first, then the current node, then the right subtree.
• Preorder (Root, Left, Right): Process the current node first, then the left subtree, then the right subtree.
• Postorder (Left, Right, Root): Process the left subtree, then the right subtree, then the current node last.

Here is a concrete example:

1        1
2       / \
3      2   3
4     / \
5    4   5

• Inorder: 4, 2, 5, 1, 3
• Preorder: 1, 2, 4, 5, 3
• Postorder: 4, 5, 2, 3, 1

Recursive Implementations

The recursive code for each traversal is almost identical - the only difference is where you place the "process" line:

Notice the pattern: the recursive structure is identical in all three. You always recurse on root.left and root.right. You always check if not root as the base case. The only thing that moves is the line where you process root.val. This is why interviewers expect you to know all three - if you understand one, you understand the template for all of them.

Why Inorder Matters for BSTs

Inorder traversal has a special property on binary search trees: it visits nodes in sorted order. If a BST contains values 1, 2, 3, 4, 5, an inorder traversal produces exactly 1, 2, 3, 4, 5. This is not a coincidence - it follows directly from the BST property (left child < parent < right child). The left subtree contains all smaller values, the current node is the next value in sequence, and the right subtree contains all larger values.

This property makes inorder traversal the go-to tool for BST problems:

• Validate a BST: Perform an inorder traversal and check that each value is greater than the previous.
• Kth smallest element: Perform an inorder traversal and stop at the kth node.
• Convert BST to sorted array: Inorder traversal directly produces the sorted sequence.

When to Use Preorder

Preorder traversal processes the root before its children. This makes it the natural choice when you need to capture the structure of the tree from the top down:

• Serialize a tree: Preorder visits the root first, so the serialized output starts with the root. To deserialize, you read the root, then recursively build the left and right subtrees. Preorder serialization with null markers can uniquely reconstruct any binary tree.
• Copy a tree: Process the current node (create a copy), then recursively copy the left and right subtrees.
• Print tree structure: Preorder naturally produces a top-down representation of the tree hierarchy.

When to Use Postorder

Postorder traversal processes children before the parent. This is essential when the answer at a node depends on the answers from its children:

• Compute height: The height of a node is 1 + max(height of left child, height of right child). You must compute the children's heights first.
• Delete a tree: Delete children before the parent, otherwise you lose access to the children.
• Evaluate expression trees: Evaluate operands (leaves) before applying the operator (internal node).
• Compute subtree sums or sizes: Sum of a subtree = left sum + right sum + current value. Children first, then combine.

Watch how inverting a tree swaps left and right children at every node from the bottom up:

The pattern here is fundamental: if computing the answer at a node requires answers from its subtrees, you need postorder. This is the single most important insight for solving tree problems, and it will reappear in the path and depth section of this lesson.

Collecting Results

In practice, you often want to collect traversal results into a list rather than printing them. The pattern is the same - just append to a list:

This helper-with-closure pattern appears constantly in tree problems. The outer function creates the result container, the inner function does the recursion, and the outer function returns the result. Get comfortable with it - you will use it in almost every tree problem.

Depth-first traversals dive deep into one branch before exploring others. Level-order traversal takes the opposite approach - it visits every node at depth 0, then every node at depth 1, then depth 2, and so on. This is breadth-first search (BFS) applied to a tree, and it uses a queue instead of a stack (or recursion).

Why does this matter? Because many tree problems are naturally level-based. Finding the minimum depth, computing level averages, or producing a right-side view of a tree all require processing nodes level by level. DFS can solve these problems, but BFS makes them straightforward because the level structure is explicit in the algorithm.

The BFS Template

The core idea: start with the root in a queue, then repeatedly dequeue a node, process it, and enqueue its children. This naturally processes nodes in level order because a queue is FIFO - nodes added earlier (from higher levels) are processed before nodes added later (from lower levels).

Step through the traversal interactively - watch how nodes are visited level by level:

The critical detail is level_size = len(queue) at the start of each iteration. This captures how many nodes belong to the current level before you start adding children (which belong to the next level). Without this, you would not know where one level ends and the next begins.

Why a Queue and Not a Stack?

This is a question worth thinking about deeply. A queue processes the oldest item first (FIFO). When you add the root, then its children, then their children, FIFO ensures you visit all nodes at depth d before any node at depth d+1. If you replaced the queue with a stack (LIFO), you would get depth-first behavior instead - the most recently added node (a child at a deeper level) would be processed next, diving deep before finishing the current level.

The data structure you use for the frontier determines the search order:

• Queue (FIFO) = Breadth-first: process level by level
• Stack (LIFO) = Depth-first: dive deep before exploring siblings

Applications

Level-order traversal is the foundation for several common tree problems:

Level averages: Compute the average value at each level. Use the BFS template and average the values in current_level.

Right-side view: For each level, return only the rightmost node. Use the BFS template and take current_level[-1] for each level.

Zigzag traversal: Alternate between left-to-right and right-to-left at each level. Use the BFS template and reverse current_level for odd-numbered levels.

Minimum depth: The first leaf node encountered during BFS is at the minimum depth. BFS guarantees this because it processes shallower levels first.

Notice how clean the minimum depth solution is with BFS - the first leaf you encounter is guaranteed to be at the shallowest depth. A DFS solution would need to explore the entire tree to confirm the minimum, making the logic more complex even though the worst-case time complexity is the same.

Time and Space Complexity

Level-order traversal visits every node exactly once, so the time complexity is O(n). The space complexity is O(w) where w is the maximum width of the tree - the largest number of nodes at any single level. For a complete binary tree, the last level has roughly n/2 nodes, so the space is O(n). For a skewed tree, the width is 1 at every level, so the space is O(1).

Compare this to DFS, which uses O(h) space where h is the height. For balanced trees, DFS uses O(log n) space while BFS uses O(n) space. For skewed trees, DFS uses O(n) space while BFS uses O(1). Neither is universally better - the right choice depends on the tree shape and the problem requirements.

Recursive traversals are elegant and match the recursive structure of trees perfectly. So why learn iterative versions? Because recursion has a hidden cost that becomes a real problem at scale: the call stack.

Every recursive call pushes a frame onto the call stack. For a balanced tree with a million nodes, the recursion depth is about 20 - no problem. But for a skewed tree with a million nodes, the recursion depth is a million. Python's default recursion limit is 1000. Even in languages without a hard limit, a million stack frames consume megabytes of memory and risk a stack overflow.

Iterative traversals replace the implicit call stack with an explicit stack data structure that you control. The logic is more verbose, but you gain two things: protection against stack overflow and the ability to control exactly what goes on the stack.

Iterative Preorder

Preorder is the easiest to convert to iterative because the root is processed first - you do not need to defer any work.

The key insight is pushing the right child before the left child. Since a stack is LIFO, the left child gets popped (and processed) first. This produces the correct preorder sequence: root, left subtree, right subtree.

Iterative Inorder

Inorder is trickier because you must defer processing the current node until after you have fully explored its left subtree. The pattern uses a pointer curr that drives down to the leftmost node while pushing everything onto the stack:

Walk through this mentally: you push the root, then its left child, then its left-left child, all the way down. When curr becomes None, you pop the stack (the leftmost node), process it, then move to its right child. If the right child exists, the inner while loop pushes it and all its left descendants. If not, you pop the next node from the stack (the parent).

This pattern is essential for BST problems like "kth smallest element" where you need inorder traversal with early termination - something that is awkward with recursion.

Iterative Postorder

Postorder is the hardest to do iteratively because the root is processed last, after both subtrees. There are multiple approaches, but the cleanest uses a two-stack method or a single stack with reversal:

This is a clever trick: notice the loop body is almost identical to iterative preorder, except left and right are swapped. The loop produces the order Root-Right-Left (a modified preorder). Reversing this gives Left-Right-Root, which is postorder. This approach is much simpler to remember than tracking "has the right subtree been visited" with flags.

Morris Traversal: O(1) Space

Both recursive and iterative traversals use O(h) space - recursion uses the call stack, iteration uses an explicit stack. Can you do better? Morris traversal achieves O(1) space by temporarily modifying the tree structure.

The idea: before visiting the left subtree, create a temporary link from the inorder predecessor back to the current node. This link acts as a "bookmark" that lets you return to the current node after finishing the left subtree, without a stack.

Morris traversal is O(n) time and O(1) space. The tradeoff is that it temporarily modifies the tree (which must be restored). In concurrent environments or when the tree is read-only, Morris traversal is not safe. It is worth knowing for interviews where the interviewer asks "can you do it in O(1) space?" but iterative traversal with an explicit stack is the practical default.

When to Use Which

In interviews, start with the recursive solution for clarity, then offer the iterative version if the interviewer asks about space optimization or production concerns. Mentioning Morris shows depth of knowledge.

Now that you understand the three traversal orders and how to implement them both recursively and iteratively, it is time to apply them to the most common category of tree interview problems: computing properties that depend on paths and depths. These problems share a pattern - the answer at each node depends on the answers from its children. That makes them postorder problems at their core, even when the recursive code does not look like a textbook postorder traversal.

Maximum Depth

The maximum depth (or height) of a binary tree is the number of edges on the longest path from the root to a leaf. This is the warmup problem for tree recursion, and it encodes the postorder pattern perfectly.

The key insight: the maximum depth of a tree rooted at node n is 1 + max(depth(n.left), depth(n.right)). You cannot compute the depth of the current node without first knowing the depths of both children. That is postorder - compute children's answers first, then combine.

Step through the recursion and see how depth bubbles up from leaves to root:

This function returns 0 for an empty tree, 1 for a single node, and recursively computes the depth for anything larger. Every tree problem you solve will follow some variation of this template: base case, recurse on children, combine results.

Path Sum

Given a root and a target sum, determine if any root-to-leaf path has values that add up to the target. This is a preorder problem - you pass information downward (the remaining sum) rather than collecting information upward.

The strategy: subtract the current node's value from the target, then check if either subtree has a path with the remaining sum. At a leaf, check if the remaining sum is exactly 0. This top-down approach passes the "remaining budget" to each child, which is the preorder pattern - process the current node first (subtract its value), then recurse on children.

Diameter of a Binary Tree

The diameter is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. It is measured in number of edges.

This is the problem where the postorder pattern truly shines and where many people get stuck. The diameter through any node is left_height + right_height - the longest path going down through the left child plus the longest path going down through the right child. The overall diameter is the maximum of this value across all nodes.

Watch how heights are computed bottom-up and the diameter is tracked at each node:

Notice the dual purpose of the height function. It returns the height (for the parent to use) but also computes the diameter through the current node as a side effect. This "return one thing, update another" pattern appears in many tree problems. The max_diameter list is used instead of a simple variable because Python closures cannot rebind variables in the enclosing scope (without the nonlocal keyword).

The Postorder Pattern in Path Problems

All three problems above share a structure:

1. Base case: Empty node returns a default value (0 for depth and height, False for path sum).
2. Recurse on children: Get the left and right answers.
3. Combine: Use the children's answers to compute the current node's answer.

For maximum depth: combine = 1 + max(left, right).

For diameter: combine = update global max with left_h + right_h, return 1 + max(left_h, right_h).

For path sum: combine = left_result or right_result.

Once you recognize this pattern, you can solve new problems by filling in the "combine" step. What is the maximum path sum? Combine = update global max with left_gain + right_gain + node.val, return node.val + max(left_gain, right_gain). What is the size of the largest BST subtree? Combine = check BST validity using children's min/max, return size accordingly. The template is always the same.

Thinking Recursively About Trees

The single most important skill in tree problems is thinking at the single-node level. Do not try to simulate the recursion in your head for the full tree. Instead, ask three questions:

1. What information do I need from my children? (heights, sums, validity)
2. What do I compute at the current node using that information? (diameter, path sum check)
3. What do I return to my parent? (height, subtree sum, validity flag)

If you can answer these three questions, you can write the recursive function. The recursion handles the rest - it visits every node and ensures children are processed before parents (postorder) or parents before children (preorder), depending on how you structure the calls.

Memorize this template. It is the skeleton of at least a dozen common tree interview problems.