# Binary Trees and Traversals > Master binary tree traversal — inorder, preorder, postorder, and level-order — and the recursive mindset that makes dozens of tree problems click instantly. Canonical: https://ironclad.academy/dsa/structures/binary-tree | Difficulty: medium | Topics: Trees, Binary Trees, Traversals, Recursion, BFS, DFS, Data Structures Asked at: Amazon, Meta, Google ## Key takeaways - A binary tree is defined recursively — every node is itself the root of a subtree, which is why recursive solutions feel so natural. - Inorder: left → root → right. Preorder: root → left → right. Postorder: left → right → root. The name tells you when root is visited. - Level-order traversal uses a queue, not recursion — it processes nodes row by row, which makes it the right tool for shortest-path and level-aware problems. - The height of a balanced tree is O(log n); a pathological (skewed) tree degrades to O(n) — this is why balance matters for BSTs and heaps. - Dozens of tree problems reduce to one template: handle the base case (null), recurse left, recurse right, combine. Internalize that skeleton and the variations come for free. > **In one line:** A binary tree is a recursive structure of nodes where each node has at most two children — and the four traversal orders (inorder, preorder, postorder, level-order) are the fundamental vocabulary for every tree problem you will ever face. Binary trees show up in more interview problems than almost any other structure. Not because they are exotic — because they are everywhere under the hood: expression parsers, file systems, database indexes, HTML DOMs. The *generic* binary tree (no ordering constraint yet) is where you learn the traversal patterns that carry over to [binary search trees](/dsa/structures/binary-search-tree), [heaps](/dsa/structures/heap), and every tree variant after. The core idea is that every tree problem is actually a *recursion* problem in disguise. The tree's shape and the recursive call stack mirror each other exactly — once you see that, the four traversals stop feeling like things to memorize and start feeling obvious. [Interactive visualizer on the original page: bst — Press 'in-order walk' and step through left → root → right] The widget is our BST visualizer doing double duty — ignore its ordering talk for now; the traversal mechanics are identical for any binary tree. Press "in-order walk" and step through: the leftmost leaf comes out first, then its parent, then that parent's right child. Every visit waits until the entire left subtree below it is done, and that pending work lives on the call stack — which can grow as deep as the tree is tall. Stack depth equals tree height, and that relationship governs the space complexity of every recursive traversal. ## What even is a binary tree? Here is a pop quiz: you have written a `max(a, b)` call. That is a binary tree. Root is `max`, left child is `a`, right child is `b`. You have used a tree. A binary tree is any structure where: 1. There is one **root** node. 2. Every node has at most a **left child** and a **right child** — zero, one, or two, never more. 3. There are no cycles, and every non-root node has exactly one parent. That is the whole definition. Nothing about ordering. Nothing about balance. Just: one root, two child slots per node, no loops. The moment you add an ordering rule ("left < root < right") you have a [binary search tree](/dsa/structures/binary-search-tree). Right now we are staying general, because the traversal patterns you need to learn first have nothing to do with ordering. ```mermaid flowchart TD A["40\n(root)"] --> B["20"] A --> C["60"] B --> D["10"] B --> E["30"] C --> F["50"] C --> G["70"] style A fill:#7c5cff,color:#fff style B fill:#22d3ee,color:#0a0a0f style C fill:#22d3ee,color:#0a0a0f style D fill:#00ff9d,color:#0a0a0f style E fill:#00ff9d,color:#0a0a0f style F fill:#00ff9d,color:#0a0a0f style G fill:#00ff9d,color:#0a0a0f ``` A few vocabulary words worth locking in, because interviewers throw them around: - **Height** of a node: the number of edges on the longest downward path from that node to a leaf. Height of the whole tree = height of the root. - **Depth** of a node: the number of edges from the root down to that node. Root has depth 0. - **Leaf**: a node with no children. - **Full** tree: every node has 0 or 2 children — no node has exactly one child. - **Complete** tree: every level is filled left-to-right, with only the last level potentially incomplete. This is the shape a [heap](/dsa/structures/heap) maintains. - **Perfect** tree: full AND complete. Every internal node has two children, all leaves at the same depth. A perfect tree with height `h` has exactly `2^(h+1) - 1` nodes. The distinction between these matters because **balance governs performance**. A balanced tree of `n` nodes has height `O(log n)`. A degenerate tree (every node has one child — basically a linked list) has height `O(n)`. Every tree operation's cost scales with height, so a skewed tree silently degrades O(log n) expectations into O(n) reality. This is the whole motivation behind AVL trees, red-black trees, and why you need the heap's complete-tree invariant. ## The recursive mindset: the key that unlocks everything Before showing you the four traversals, here is the mental model that makes all of them obvious rather than memorized. A binary tree is **recursively defined**. In code, a node looks like this: ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ``` A "tree" is either `None` (an empty tree) or a `TreeNode` whose `left` and `right` are themselves trees. The structure *calls itself*. And that means any function over a tree can call itself on the left subtree and the right subtree, and the base case is just `None`. The skeleton is always: ```python def solve(node): if node is None: # base case: empty subtree return ... # some identity value (0, True, None, [], ...) left_result = solve(node.left) # recurse left right_result = solve(node.right) # recurse right return combine(node.val, left_result, right_result) ``` Nearly every tree problem on LeetCode fits this shape. Height of a tree? `combine = 1 + max(left, right)`. Count nodes? `combine = 1 + left + right`. Check if balanced? `combine = abs(left_height - right_height) <= 1 and left_ok and right_ok`. The skeleton does not change. Only `combine` changes. The four traversals are all just different choices of *when to process the current node* relative to the recursive calls. That is literally the only difference. See [crash course: recursion](/dsa/crash-course/04-recursion) if you want to build this intuition from the ground up first — it is worth it. ## The four traversals ### Depth-first: inorder, preorder, postorder All three are DFS. They visit every node exactly once, so the traversal itself is O(n) time and O(h) space (where `h` is height — the call stack can go as deep as the tree is tall). One honesty note about the snippets below: `left + [val] + right` copies both lists at every node, so these readable versions actually cost O(n·h) — O(n log n) on a balanced tree, O(n²) on a skewed one. Append to a shared list (or use a generator) to get true O(n); the iterative version further down already does. **Inorder — left → root → right** ```python def inorder(node): if node is None: return [] return inorder(node.left) + [node.val] + inorder(node.right) ``` For a *binary search tree*, inorder always yields a sorted sequence — that is its killer property. For a generic tree, it gives you the "flattened" left subtree, then the root, then the right subtree. Used for: BST validation, sorted iteration, printing an expression tree in infix notation (evaluation needs postorder — more below). **Preorder — root → left → right** ```python def preorder(node): if node is None: return [] return [node.val] + preorder(node.left) + preorder(node.right) ``` The root comes out first, before anything else. Used for: copying/serializing a tree (you need to know the root before you can reconstruct children), generating prefix expressions, printing directory structures (folder name before its contents). **Postorder — left → right → root** ```python def postorder(node): if node is None: return [] return postorder(node.left) + postorder(node.right) + [node.val] ``` The root comes out last, after both subtrees are fully processed. Used for: deleting a tree (free children before the parent), evaluating expression trees bottom-up, computing subtree sizes and heights (you need children's answers before you can compute the parent's). Here is the mnemonic that actually works: the *name* tells you when the root is visited — **pre**order visits root *before* children, **post**order visits root *after* children, **in**order visits root *in between* children. [Interactive visualizer on the original page: bst — Inorder walk: left → root → right (yields sorted order for a BST)] Step through the inorder traversal on this tree. The output order is `10, 20, 30, 40, 50, 60, 70` — sorted, because this tree happens to be a valid BST. Notice that the very first value emitted is `10`, the leftmost leaf: nothing is visited until the walk has run all the way down the left spine. ### Iterative inorder (the stack trick interviewers love) The recursive versions above are clean to write, but sometimes you need an iterative version — either to avoid stack-overflow on deep trees or because the interviewer explicitly asks for it. Here is inorder iteratively, using an explicit stack: ```python def inorder_iterative(root): result = [] stack = [] curr = root while curr or stack: # Go as far left as possible while curr: stack.append(curr) curr = curr.left # Process the node curr = stack.pop() result.append(curr.val) # Move to right subtree curr = curr.right return result ``` The pattern: push nodes as you go left, pop and process when you can't go further left, then pivot to the right subtree. This is the exact same traversal order as the recursive version — just with an explicit stack instead of the call stack. ### Level-order: BFS with a queue The three DFS traversals all go deep first — down a branch before backtracking. Level-order goes *wide* first: all nodes at depth 0, then all nodes at depth 1, then depth 2, and so on. This is breadth-first search on a tree. You cannot do this cleanly with recursion. You need a **queue**. ```python from collections import deque def level_order(root): if root is None: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) # how many nodes are on this level current_level = [] for _ in range(level_size): node = queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result ``` This returns `[[40], [20, 60], [10, 30, 50, 70]]` for our example tree — each level as its own list. The `level_size` snapshot at the start of the outer loop is the key move: it tells you how many nodes belong to the current level before you start adding their children. When do you reach for level-order over DFS? - Finding the **minimum depth** (shortest path to a leaf) — BFS reaches the shallowest leaf first, no need to explore the whole tree. - Printing or serializing the tree **level by level**. - Finding all nodes at a **specific depth**. - The **right side view** of a tree (last node on each level). - **Zigzag traversal** (alternate left-to-right and right-to-left per level). Anything that involves "levels" or "the closest X" is almost always BFS. Anything that involves "all paths", "subtree structure", or "computing a value from children" is almost always DFS. ## Complexity: the height problem | Traversal | Time | Space | Notes | |---|---|---|---| | Inorder (recursive) | O(n) | O(h) | call stack depth = height | | Preorder (recursive) | O(n) | O(h) | same | | Postorder (recursive) | O(n) | O(h) | same | | Level-order (BFS) | O(n) | O(w) | w = max width ≈ n/2 at last level for a perfect tree | The `O(h)` space for DFS and `O(w)` for BFS diverge sharply depending on tree shape — and the trade-off flips. For a balanced tree, DFS wins: the call stack holds O(log n) frames, while the BFS queue peaks at the bottom level, which alone holds roughly n/2 nodes — O(n), exponentially worse. For a degenerate skewed tree it inverts: the DFS call stack hits every node (O(n)) while the BFS queue never holds more than one node per level, O(1). When memory matters, pick by shape: bushy tree → DFS, linked-list-shaped tree → BFS. ## A full worked example: diameter of a binary tree The diameter of a tree is the length of the longest path between any two nodes (the path may or may not pass through the root). This is a good representative problem because the naive approach is obvious but wrong, and fixing it requires understanding postorder. ```python def diameter_of_binary_tree(root): # We need the height of each subtree AND we need to update the # diameter as we go — this is postorder: handle children first. max_diameter = 0 def height(node): nonlocal max_diameter if node is None: return 0 left_h = height(node.left) # postorder: left first right_h = height(node.right) # then right # The longest path through this node = left_height + right_height max_diameter = max(max_diameter, left_h + right_h) return 1 + max(left_h, right_h) # height of this subtree height(root) return max_diameter ``` The subtle insight: you cannot compute the diameter at the root and call it done — the longest path might go through any node in the tree. So you run the `height` recursion (which is postorder — you need child heights before computing the current node's height) and update a running max at every node. Single O(n) pass, O(h) space. This is a template. Swap `max_diameter` for "path sum" and you get maximum path sum. Swap for a count of valid paths and you get path sum equals target. Same skeleton, different accumulator. ## Common pitfalls **Forgetting the null base case.** Every recursive tree function needs to handle `node is None` first, or you will get an AttributeError the moment you hit a leaf's missing child. Do not skip this even when it seems obvious. **Assuming inorder output is sorted.** It is — but only for a *binary search tree*. For an arbitrary binary tree, inorder gives you one particular traversal order, nothing more. Do not conflate generic binary trees with BSTs. **Confusing height and depth.** Height measures from a node *down* to the farthest leaf. Depth measures from the root *down* to the node. They use the same word "down" and trip people up constantly. Height of root = height of tree. Depth of root = 0. **Stack overflow on skewed trees.** A linked-list-shaped tree of 100,000 nodes will blow Python's default recursion limit (~1000 frames). In an interview, mention you know this and would use an iterative approach with an explicit stack for production code. In Python specifically, you can also raise the limit with `sys.setrecursionlimit`, but that is a hack, not a fix. **Using BFS when you meant DFS (or vice versa).** If the problem asks for "all root-to-leaf paths", BFS makes this annoying because you have to carry partial paths in the queue. DFS (preorder) is the natural fit. Conversely, "minimum depth" with DFS requires visiting the whole tree; BFS finds it immediately when the first leaf dequeues. ## When NOT to use a generic binary tree A plain binary tree with no structural guarantees is rarely what you want in production code. It is mainly a conceptual foundation and an interview substrate. Once you know what you need: - **Need fast O(log n) search, insert, delete?** Use a [binary search tree](/dsa/structures/binary-search-tree) — the ordering invariant is what makes those operations fast. - **Always need the min or max element?** Use a [heap](/dsa/structures/heap) — it is a complete binary tree with a weaker but cheaper invariant than a BST. - **Need multi-level lookups (like a filesystem)?** A general n-ary tree, trie, or B-tree is likely a better fit. The generic binary tree is not a production data structure so much as a *problem type*. Almost every "tree problem" in an interview is really asking: "do you understand recursion on a hierarchical structure?" Answer yes convincingly, and the rest is pattern recognition. The patterns, in short: inorder for sorted iteration / BST validation, preorder for copying / serialization, postorder for bottom-up aggregation, level-order for level-aware or shortest-path problems. Master the recursive skeleton `solve(node) → combine(solve(left), solve(right))` and you will recognize the variation each problem needs in under a minute. ## Frequently asked questions Q: What are the four ways to traverse a binary tree? A: Inorder (left → root → right), preorder (root → left → right), postorder (left → right → root), and level-order (BFS, row by row using a queue). The first three are depth-first and are naturally expressed with recursion. Level-order is breadth-first and needs a queue to process nodes layer by layer. Q: What is the difference between inorder, preorder, and postorder traversal? A: The difference is when you "visit" (process) the current node relative to its children. Preorder visits the node first, then recurses into children — useful for copying or serialising a tree. Inorder visits left child, then the node, then right child — for a binary search tree this yields sorted order. Postorder visits both children before the node — useful for deletion or evaluating expression trees, because you need child results before you can handle the parent. Q: Why is recursion the natural tool for binary trees? A: A binary tree is a recursive structure by definition: a tree is either empty, or a root node with a left subtree and a right subtree — each of which is itself a tree. This structural self-similarity maps directly onto recursive functions, where each call handles the current node and delegates the subtrees to itself. The call stack mirrors the tree structure, which is why tree problems almost always have a clean recursive solution. Q: What is the difference between a full, complete, and perfect binary tree? A: A full tree has every node with 0 or 2 children (no node has exactly one). A complete tree fills each level left to right, with the last level possibly incomplete — this is what a heap uses. A perfect tree is both full and complete: every internal node has exactly 2 children and all leaves are at the same depth. Perfect trees have exactly 2^(h+1)−1 nodes for height h. Q: When should I use BFS (level-order) instead of DFS for tree problems? A: Choose BFS when the problem cares about depth or level structure: finding the shortest path to a leaf, printing nodes level by level, finding the minimum depth, or checking if a tree is symmetric. DFS (the three recursive orders) is better when the problem involves a full path from root to leaf, subtree structure, or any computation that needs children results before parents (postorder). If unsure, DFS is usually simpler to write.