Skip to content
Tutorials Center
My learning

Topics

Lesson 91 of 225 ยท Trees

Tree Traversals

Learn preorder, inorder and postorder tree traversal in Python, both recursive and iterative, plus Morris traversal and rebuilding a tree from two traversals.

A traversal visits every node of a tree exactly once, in a well-defined order. Arrays and linked lists have one natural order (front to back). Trees have several, because at every node you must decide: do I handle this node before its subtrees, between them, or after them? Those three choices give the three classic depth-first traversals: preorder, inorder and postorder. Each one answers different problems, and knowing which to reach for is half of solving a tree question.

This lesson shows all three recursively (three lines each), then converts them to iterative versions with an explicit stack, sketches the clever O(1)-space Morris traversal, and ends with a classic puzzle: rebuilding a tree when you only know two of its traversals. Breadth-first order has its own lesson: level-order traversal.

The three orders

Take this tree:

TEXT
        1
       / \
      2   3
     / \   \
    4   5   6

The only difference between the traversals is when you process the current node:

Order Rule Result for the tree above
Preorder node, left, right 1 2 4 5 3 6
Inorder left, node, right 4 2 5 1 3 6
Postorder left, right, node 4 5 2 6 3 1

A memory trick: the name tells you where the node goes relative to its children. Pre = before, in = between, post = after. Left always comes before right.

Python Recursive preorder, inorder and postorder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three run in O(n) time: every node is visited once and does O(1) work. The space is the recursion depth, O(h), where h is the height of the tree.

Which order for which job?

  • Preorder processes a parent before its children. Use it to copy a tree, to serialize it, or to print a directory listing where the folder comes before its contents.
  • Inorder on a binary search tree yields the keys in sorted order. That fact alone makes it the most important of the three.
  • Postorder processes children before the parent. Use it when a node's answer depends on its subtrees' answers: computing sizes and heights, evaluating an expression tree, or deleting a tree safely (free the children first).
Python Preorder vs postorder in practice

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Iterative traversals with a stack

Recursion uses the call stack behind the scenes. Python caps that stack at about 1000 frames, so a skewed tree with a few thousand nodes breaks the recursive versions. The fix is to manage the stack yourself, which also shows what the recursion was really doing.

Preorder is the easiest. Push the root. Repeatedly pop a node, record it, then push its right child and then its left child, so the left one is popped first.

Inorder needs more care: go as far left as possible, pushing every node you pass. When you cannot go further left, pop, record, and move to the right child.

Postorder is the awkward one. A neat trick: do a "node, right, left" preorder (push left before right), then reverse the result. Reversing "node, right, left" gives "left, right, node".

TEXT
Inorder with a stack on the example tree:

 slide left, pushing:  stack [1, 2, 4]
 pop 4, record 4          (4 has no right child)
 pop 2, record 2, go right to 5, push 5
 pop 5, record 5
 pop 1, record 1, go right to 3, push 3
 pop 3, record 3, go right to 6, push 6
 pop 6, record 6          -> 4 2 5 1 3 6
Python Iterative traversals with an explicit stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time is still O(n). Space is O(h) for the stack (O(n) in the worst case for the skewed tree, but without any recursion limit).

When an interviewer asks "do it iteratively", the stack versions above are the expected answer. If they ask for "O(1) extra space", the answer is Morris traversal.

Morris traversal: no stack at all

Both the recursive and the stack-based traversals need O(h) memory to remember where to return to after finishing a left subtree. Morris traversal removes that memory by borrowing space that is already there: the empty right pointer of the rightmost node in a left subtree. It temporarily points that pointer back to the current node (a thread), so after finishing the left subtree you can walk back up through the thread. Afterward the thread is removed and the tree is exactly as before.

The algorithm for inorder, with cur starting at the root:

  1. If cur has no left child: record cur, move to cur.right.
  2. Otherwise find the predecessor: the rightmost node in cur.left.
  3. If the predecessor's right is empty: set it to cur (create the thread) and move to cur.left.
  4. If it already points to cur: the left subtree is finished. Remove the thread, record cur, and move to cur.right.
Python Morris inorder traversal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Morris runs in O(n) time (each edge is walked at most about twice) and O(1) extra space. The price is complexity, and the tree is briefly modified, so it is unsafe if other threads read the tree at the same time.

Rebuilding a tree from two traversals

One traversal alone does not identify a tree: a left child and a right child can give the same preorder list. But preorder + inorder (or postorder + inorder) with distinct values determines the tree uniquely.

The idea for preorder + inorder:

  1. The first preorder value is the root.
  2. Find that value in the inorder list. Everything to its left is the left subtree; everything to its right is the right subtree.
  3. The left subtree's size tells you how many of the next preorder values belong to it. Recurse on both parts.
TEXT
preorder: [1, 2, 4, 5, 3, 6]      inorder: [4, 2, 5, 1, 3, 6]
root = 1 -> inorder splits into [4, 2, 5] | 1 | [3, 6]
left has 3 nodes -> preorder splits into [2, 4, 5] | [3, 6]

A dictionary from value to inorder position removes the linear search, so the whole build is O(n) instead of O(n^2).

Python Rebuild a tree from preorder and inorder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the order of the recursive calls. With preorder you consume values root, left, right, so you must build the left subtree first. Reading postorder from the end gives root, right, left, so the right subtree is built first. Swapping those two lines is the most common bug here.

Preorder + postorder alone is not enough in general: a node with a single child could be a left or a right child, and both give identical lists. It works only for full binary trees.

More traversal patterns

Interviews love variations on these three orders. Each one is the same walk with a little bookkeeping. All examples below use this sample tree:

TEXT
          1
        /   \
       2     3
      / \   / \
     4   5 6   7
        /       \
       8         9

In code it is TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5, TreeNode(8))), TreeNode(3, TreeNode(6), TreeNode(7, None, TreeNode(9)))).

Boundary traversal

The boundary of a tree is what you would see if you walked around its outline counter-clockwise: the left boundary from the root downward, then the leaves from left to right, then the right boundary from the bottom back up to the root. Three rules keep it honest:

  1. The left boundary takes the left child when it exists, otherwise the right child, and excludes leaves (they are collected in step 2).
  2. The leaves come from an ordinary traversal that records nodes with no children.
  3. The right boundary is collected the same way as the left one, then reversed, and excludes leaves and the root.

Vertical order traversal

Give every node a horizontal distance (hd): the root has 0, a left child has hd - 1, a right child has hd + 1. Nodes with the same hd lie on the same vertical line. A breadth-first walk that carries the hd and collects nodes into a dictionary keyed by hd lists each line top to bottom. Sort the keys at the end to read the lines from left to right.

Diagonal traversal

Here a left child starts a new diagonal (d + 1), while a right child stays on the same diagonal (d). Nodes sharing a diagonal id lie along a line running down and to the right, like the slashes in the picture above. The same one-pass idea gives them all.

Python Boundary, vertical and diagonal traversals

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A few details matter. In vertical, nodes that share both a column and a row come out left to right (the queue order), which is what most problem statements want; some versions break ties by value instead, so read the statement. In boundary, a tree consisting only of the root returns just the root.

Building a tree from inorder and level order

Preorder or postorder with inorder is not the only pair that works. Inorder + level order also determines a tree with distinct values. The first value of the level order is the root. Find it in the inorder list and split that list into a left and a right part. Then split the level order into two lists by keeping the original order of the values that belong to each side, and recurse. The straightforward version costs O(n^2) because of the repeated filtering.

Rebuilding from an ancestor matrix

An ancestor matrix is an n by n table where m[i][j] = 1 means node i is an ancestor of node j. The number of ones in row i is the number of descendants of i. Sort the nodes by that count, smallest first: a node with fewer descendants sits lower in the tree. Process them in that order: for each node i, every j it is an ancestor of that has no parent yet becomes its child. The last node processed (the most descendants) is the root.

Minimum time to burn a tree

Set fire to a node. Each minute the fire spreads from a burning node to its parent and its children. How long until the whole tree burns? A tree node has no parent pointer, so first record every node's parent in a dictionary, then run a breadth-first search from the burning node over the three neighbors (left, right, parent). The number of BFS levels, minus one for the starting level, is the answer.

Python Inorder + level order, ancestor matrix, and burning a tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity summary

Traversal Time Extra space
Recursive (any order) O(n) O(h) call stack
Iterative with a stack O(n) O(h)
Morris inorder/preorder O(n) O(1)
Rebuild from two traversals (with a map) O(n) O(n)
Boundary, vertical, diagonal O(n), plus O(k log k) to sort k columns O(n)

Common mistakes

  • Wrong push order in iterative preorder. The stack reverses order: push right first so that left is processed first.
  • Mixing the three orders when writing the recursion. Only the position of the "record" line changes; keep the left, right calls in that order.
  • Forgetting that the rebuilt tree needs distinct values. With duplicates, the position of a value in the inorder list is ambiguous.
  • Using list concatenation recursively for big trees. preorder(l) + preorder(r) copies lists at every level; append to one shared list instead.
  • Leaving Morris threads in place if you stop early. Always finish the loop, or undo threads before returning.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which traversal of a binary search tree visits the keys in sorted order?

    Inorder visits left subtree (smaller keys), then the node, then the right subtree (larger keys), which is ascending order.
  2. 2. A tree has preorder [1, 2, 3] and inorder [3, 2, 1]. What does the tree look like?

    1 is the root. In the inorder list everything else is to its left, so 2 and 3 form the left subtree, and the same argument repeats: 1 -> left 2 -> left 3.
  3. 3. In the iterative preorder traversal, why is the right child pushed before the left child?

    The most recently pushed node is popped first. Pushing left last means left is visited before right.
  4. 4. What is the extra space of Morris traversal?

    It uses the empty right pointers of leaves-in-waiting as temporary threads instead of a stack.
  5. 5. When rebuilding a tree from postorder and inorder, which subtree must be built first?

    Reading postorder from the end yields root, right subtree, left subtree, so the right subtree consumes its values first.

Summary

  • Depth-first traversals differ only in when the node is processed: preorder (before), inorder (between), postorder (after).
  • Recursive traversals are three lines each; they run in O(n) time and O(h) stack space.
  • Preorder suits copying and serializing, inorder gives sorted order on a BST, postorder suits bottom-up computations.
  • Iterative versions use an explicit stack; postorder is a reversed "node, right, left" walk.
  • Morris traversal achieves O(1) extra space by temporarily threading predecessor pointers.
  • Preorder (or postorder) plus inorder rebuilds a tree with distinct values; a value-to-index map keeps it O(n).
  • Boundary, vertical and diagonal traversals are one walk that tracks an extra number (side, horizontal distance, diagonal id); burning a tree is a BFS over left, right and parent.

Next: Level-Order Traversal and Tree BFS