Binary Tree Traversals

Trees, Heaps and Tries · 30 min

DSA · Binary trees

Four traversals, one recursion

Preorder, inorder and postorder are one walk with the print line moved to three places. Level order needs a queue.

Step through the recursion on a live tree →
One tree, four answers. preorder 5 3 1 4 8 7 9 · inorder 1 3 4 5 7 8 9 · postorder 1 4 3 7 9 8 5 · level order 5 3 8 1 4 7 9

01 The idea

A traversal is a rule for the order you print

An array has one obvious order: left to right. A tree does not. From node 5 you can go left, or you can go right, and whichever you pick you still owe the other side a visit. A traversal is the fixed rule that settles that argument for every node in the tree.

Three of the four traversals are depth-first: they dive to the bottom of one branch before touching the next. Written as recursion they are built from the same three moves — deal with the left child, deal with the right child, print this node — and left is always dealt with before right. The only thing that changes between them is where the print sits relative to those two calls. Level order is the odd one out: it refuses to dive at all and reads the tree row by row, which recursion cannot do on its own.

Every depth-first traversal takes the identical route through the tree. Move the print statement to the front, the middle, or the end of the function and you get preorder, inorder, or postorder.
Node, child, leafA node holds a value and up to two links, called left and right. A node with no links is a leaf. In our tree 1, 4, 7 and 9 are leaves.
SubtreeA node plus everything hanging below it. The subtree rooted at 3 is the set {3, 1, 4}, and a recursive call gets handed exactly one subtree.
Base caseThe call that stops the recursion. Here it is node is null — you have run off the bottom of the tree, so return without printing.

02 Hand trace

Inorder, by hand, on a 7-node tree

This is the tree the whole lesson uses. Seven nodes, values under 10, and it happens to be a binary search tree — every value on the left of a node is smaller, every value on the right is larger.

        5          <- root      /   \     3     8    / \   / \   1   4 7   9     <- leaves

Now run inorder on it: left, then this node, then right. Follow the output row as it fills. A dot means that slot has not been printed yet.

at 5, then 3·······left comes first — nothing printed yet
at 11······no left child → print 1
back at 313·····left side done → print 3
at 4134····no left child → print 4
back at 51345···whole left subtree done → print 5
right half1345789same rule under 8: 7, then 8, then 9
result1345789sorted — because the tree is a BST

Look at the route your finger took, not the numbers: down the left as far as it goes, back up one, out to the right, back up again. Preorder and postorder take that exact same route. They print 5 first, or 5 last, instead of printing it in the middle — and that single difference is the whole of section 03.

03 The code

One function, three print positions — and a queue for the fourth

Write the depth-first walk once. Keep exactly one of the three print lines and delete the other two; you have chosen your traversal. Level order cannot be written this way, so it gets its own loop on the right.

Depth-first · the one recursion

function walk(node):  if node is null: return      # base case  print node.value    # 1 -> PREORDER  walk(node.left)  print node.value    # 2 -> INORDER  walk(node.right)  print node.value    # 3 -> POSTORDER

Level order · a queue, no recursion

function levelOrder(root):  if root is null: return  q = new queue holding root  while q is not empty:    node = q.removeFirst()    print node.value    if node.left: q.add(node.left)    if node.right: q.add(node.right)

Why one function and not three. The route is identical in all three orders, so three separate functions would duplicate the same two recursive calls and hide the only real difference. In an interview you want to answer "where does the print go?" in one sentence, and this shape is that sentence.

Why the null check is line 2 and not inside the caller. Node 1 is a leaf, but it still calls walk on two null children. Checking inside the callee means you write the guard once instead of at all three call sites — the two recursive calls and the first call on the root. It also explains the call count: our 7-node tree makes 15 calls, not 7.

Why level order needs a queue, not recursion. Recursion is a stack — last in, first out — so it always dives deeper before it comes back. Level order needs the opposite: finish row one completely before touching row two. A queue is first in, first out, which is exactly that promise.

Why the print line moves but walk(node.left) never does. Left is always taken before right in all four traversals. Swap those two lines instead of moving the print and you get the three mirror-image traversals, which is a standard follow-up question.

TraversalRuleOutput on our tree
Preordernode, left, right5 3 1 4 8 7 9
Inorderleft, node, right1 3 4 5 7 8 9
Postorderleft, right, node1 4 3 7 9 8 5
Level orderrow by row, using a queue5 3 8 1 4 7 9

05 Cheat sheet

The numbers you will be asked for

QuestionAnswerWhy
Time, any of the fourO(n)Every node is entered exactly once and does constant work besides recursing.
Calls made by a DFS walk2n + 1n real nodes plus the n+1 null links. Our 7-node tree makes 15 calls.
Extra space, recursive DFSO(h)h is the height. The call stack holds one frame per level, not per node.
Extra space, skewed treeO(n)A tree with one child per node is a linked list, so h equals n.
Extra space, level orderO(w)w is the widest level. In a perfect tree — every level completely filled — the bottom row alone is about n/2 nodes.
Inorder of a BSTsortedLeft values are all smaller and right values all larger, so they come out ascending.
Preorder copies a treeThe root arrives before its children, so a copy can create the parent before it has anything to hang below it. Serialisation uses it too — but only if you also emit a marker for every null link, since a bare preorder list does not pin down the shape.
Inorder sorts a BSTLeft, node, right on a binary search tree emits values in increasing order. Ours gives 1 3 4 5 7 8 9.
Postorder frees a treeBoth children are finished before the parent, so it is the safe order for deleting nodes and for evaluating an expression tree.

06 Where & why

Choosing an order is never about speed

All four traversals visit every node once and cost O(n). Picking between them is a question about timing: do you need a node's value before its children have been handled, after, or does only its distance from the root matter?

Reach for each one when…

Preorder — the parent must come firstSerialising a tree to a file, deep-copying it, or printing a folder listing where a directory has to appear above its contents.
Inorder — the tree is a BSTReading values in sorted order, finding the k-th smallest, or checking that a tree really is a valid search tree.
Postorder — the children must come firstDeleting a tree, computing subtree size or height, and evaluating an expression tree from the leaves upward.
Level order — depth is the answerPrinting the tree row by row, finding the shallowest leaf, or producing the right-side view of a tree.

Use something else when…

SituationBetter choiceWhy
The tree is deep and skewed — 100,000 nodes in a chainIterative DFS with your own stackRecursion runs out of stack frames after a few thousand levels. An explicit stack lives on the heap and just grows.
You need the shortest root-to-leaf pathLevel order (BFS)BFS meets nodes in increasing depth, so the first leaf it reaches is the shallowest. DFS may dive down a long branch first and find it last.
You need inorder with no stack and no recursionMorris traversalIt points the rightmost node of a left subtree — whose right pointer is null anyway — at its inorder successor, giving O(1) extra space at the cost of briefly rewiring the tree.
The structure is a graph, not a treeDFS or BFS with a visited setA tree has no cycles and no shared children, so a traversal can never revisit a node. Remove that guarantee and this exact code re-walks the same nodes — and on a cycle it never stops at all.
Interviewers rarely ask you to write a traversal. They ask which one and why — and the answer is always the position of the print statement relative to the two recursive calls.

07 Interview questions

What actually gets asked

Read the question, answer it out loud, then open the card. Each answer is about twenty seconds spoken.

What is a tree traversal?
It is a rule that fixes the order in which you visit every node exactly once. An array has one natural order, but from any tree node you can go left or right, so you need a rule. The four standard ones are preorder, inorder, postorder and level order.
What is the difference between preorder, inorder and postorder?
Only the position of the visit relative to the two recursive calls. Preorder is node, left, right, inorder is left, node, right, postorder is left, right, node. The path your code walks through the tree is identical in all three.
What is the time complexity, and why?
O(n) for all four. Every node is entered exactly once, and the work at a node is constant once you exclude the recursive calls. There is no way to be faster, because printing n values already costs n.
How much extra space does a recursive traversal use?
O(h), where h is the height of the tree, because the call stack holds one frame per level you are currently inside — not one per node. A balanced tree gives O(log n); a tree skewed into a chain gives O(n).
Why does inorder on a binary search tree come out sorted?
A BST guarantees every value in a node’s left subtree is smaller than the node and every value on the right is larger. Inorder prints the whole left subtree, then the node, then the whole right subtree, so values leave in increasing order. On our tree that is 1 3 4 5 7 8 9.
How many function calls does a DFS traversal of a 7-node tree make?
15. A binary tree with n nodes has exactly n+1 null links, and every one of them is still a call that hits the base case and returns. So the total is 2n + 1 — 7 real calls plus 8 that print nothing.
DFS or BFS on a tree — when do you pick which?
Pick DFS when the answer is about a whole subtree or a root-to-leaf path, and when memory matters: it costs O(h). Pick BFS when the answer depends on depth — shallowest leaf, row-by-row printing, right-side view — and accept O(w) memory, where the widest row of a perfect tree is about n/2 nodes.
Can you do level order without a queue?
Yes, but it costs more. Compute the height, then call a helper printLevel(node, d) once per depth, which recurses down and prints only the nodes at depth d. That re-walks the top of the tree for every level, so it is O(n·h) — up to O(n²) on a skewed tree — instead of O(n).
Given the preorder and inorder output, can you rebuild the tree?
Yes, uniquely, as long as the values are distinct. The first value of preorder is the root; find it in the inorder list and everything before it is the left subtree, everything after it is the right subtree, then recurse. Preorder plus postorder is not enough — it cannot tell whether a lone child is a left child or a right child, unless every node has 0 or 2 children.
How would you traverse a tree that is 100,000 nodes deep?
Not with recursion — most languages blow the call stack after a few thousand frames. Rewrite it iteratively with an explicit stack you push and pop yourself, which lives on the heap. If you also need O(1) extra space, Morris traversal reuses the already-null right pointer of each left subtree’s rightmost node as a temporary link up to its inorder successor.
Where have you actually used a traversal outside an interview?
Constantly, usually without naming it. Pretty-printing JSON and rendering the DOM are preorder, because the parent has to be emitted before its children. Deleting a directory tree and evaluating an expression tree are postorder, because the children have to be gone first. A file explorer that expands one level at a time is level order.

08 Practice problems

Six problems, in order of bite

Every one is solvable with the code from section 03 — the recursive walk for five of them, the queue loop for the level-order one. Check your answers against the lesson tree: 5 3 8 1 4 7 9 in level order.

Postorder from the same function

Easy
Return the postorder list of a binary tree. The only edit to the walk is moving one line — say where it goes before you write it.
Follow-up
Now produce the same list without writing a postorder function at all: run preorder with the two recursive calls swapped, then reverse the output. Check both routes agree on the lesson tree.
Show the hint
The parent prints only after both recursive calls have returned, so the print line goes below walk(node.right).

Count the leaves

Easy
Return the number of nodes that have neither a left nor a right child.
Follow-up
Nothing is printed, so there is no visit position to choose. The answer is built from what the two recursive calls return instead of from an output list.
Show the hint
A null node contributes 0, a leaf contributes 1, and anything else contributes left + right.

Height of the tree

Medium
Return the number of edges on the longest path from the root down to a leaf.
Follow-up
This is postorder in disguise: a node cannot know its height until both children have reported theirs. The statement counts edges, so a lone root must come out 0 — which forces the empty tree to -1. Run your base case on a single node and confirm it does.
Show the hint
A node’s height is one more than the taller of its two children’s, so both recursive calls have to return before the node can answer.

Level order split into rows

Medium
Return a list of lists, one list per depth, top row first. On the lesson tree that is [[5], [3, 8], [1, 4, 7, 9]].
Follow-up
The plain queue loop gives you one flat list. Splitting it into rows needs you to notice that the queue holds exactly one complete level at the top of each iteration.
Show the hint
Before the inner loop, record count = q.size() and pop exactly that many nodes.

Is this a valid BST?

Medium
Return true only if every node is larger than everything in its left subtree and smaller than everything in its right subtree.
Follow-up
Comparing a node with just its two children passes trees that are not BSTs — a grandchild can break the rule without any parent noticing. One of the four traversals hands you the fix for free.
Show the hint
Run an inorder traversal and check that every printed value is strictly greater than the one before it.

Rebuild the tree from two traversals

Hard
Given the preorder list and the inorder list of a tree with distinct values, return the tree itself.
Follow-up
This is a traversal run backwards, and it is the real reason interviewers ask about traversals at all. Then try the same thing with preorder plus postorder and construct the smallest tree where it fails.
Show the hint
The first value in preorder is the root; locate it in inorder and everything to its left is the left subtree, everything to its right is the right subtree.