AlgoScope

Tree Traversals

Every traversal visits the same nodes. The only thing that changes is when a node gets written down relative to its two subtrees. Morris walks the same inorder sequence with no stack at all: before descending into a left subtree it points the rightmost node of that subtree back at the current node, and when the walk arrives along that borrowed pointer it knows the left side is finished, removes the pointer and visits. The tree ends exactly as it started, and the extra memory is a single variable.

The player

A binary search tree with 7 nodes. Walking it in preorder order, which visits the node first, then its left subtree, then its right.20304050607080

Walk this tree in preorder order: the node first, then its left subtree, then its right.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.

  1. Which value is written down next?

    • 20
    • 50

    Answer: 50. 50 is next in preorder order. 20 is what inorder would take.

  2. Which value is written down next?

    • 30
    • 40
    • 70

    Answer: 30. 30 is next in preorder order. 40 is what postorder would take. 70 is what zigzag would take.

  3. Which value is written down next?

    • 20
    • 30
    • 40

    Answer: 20. 20 is next in preorder order. 40 is what inorder would take. 30 is what postorder would take. 70 is what level-order would take. 60 is what reverse-level would take.

  4. Which value is written down next?

    • 40
    • 50
    • 60

    Answer: 40. 40 is next in preorder order. 50 is what inorder would take. 60 is what postorder would take. 20 is what level-order would take. 80 is what reverse-level would take.

  5. Which value is written down next?

    • 60
    • 70
    • 80

    Answer: 70. 70 is next in preorder order. 60 is what inorder would take. 80 is what postorder would take. 40 is what level-order would take. 30 is what reverse-level would take.

  6. Which value is written down next?

    • 60
    • 70

    Answer: 60. 60 is next in preorder order. 70 is what inorder would take.

  7. Which value is written down next?

    • 50
    • 80

    Answer: 80. 80 is next in preorder order. 50 is what postorder would take.

How it runs, step by step

  1. Walk this tree in preorder order: the node first, then its left subtree, then its right.

    A binary search tree with 7 nodes. Walking it in preorder order, which visits the node first, then its left subtree, then its right.

  2. 50 is the root, and preorder writes a node down before going anywhere.

    Visiting 50, number 1 of 7. The order so far is 50.

  3. 30 is reached, and preorder writes it down straight away.

    Visiting 30, number 2 of 7. The order so far is 50, 30.

  4. 20 is a leaf, so there is nothing below it to do first.

    Visiting 20, number 3 of 7. The order so far is 50, 30, 20.

  5. 40 is a leaf, so there is nothing below it to do first.

    Visiting 40, number 4 of 7. The order so far is 50, 30, 20, 40.

  6. 70 is reached, and preorder writes it down straight away.

    Visiting 70, number 5 of 7. The order so far is 50, 30, 20, 40, 70.

  7. 60 is a leaf, so there is nothing below it to do first.

    Visiting 60, number 6 of 7. The order so far is 50, 30, 20, 40, 70, 60.

  8. 80 is a leaf, so there is nothing below it to do first. That is the last one.

    Visiting 80, number 7 of 7. The order so far is 50, 30, 20, 40, 70, 60, 80.

  9. The preorder walk is 50, 30, 20, 40, 70, 60, 80.

    The preorder traversal visited 50, 30, 20, 40, 70, 60, 80.

The code

Tree Traversals, in Python

def inorder(n):
    if n is None: return
    inorder(n.left)
    visit(n)
    inorder(n.right)

def level_order(root):
    q = deque([root])
    while q:
        n = q.popleft()
        visit(n)
        if n.left is not None: q.append(n.left)
        if n.right is not None: q.append(n.right)

def zigzag(root):                                           # level order, alternating direction
    level = [root]; left_to_right = True
    while level:
        for n in (level if left_to_right else reversed(level)): visit(n)
        level = [c for n in level for c in (n.left, n.right) if c is not None]
        left_to_right = not left_to_right

def reverse_level_order(root):                              # bottom level first
    stack = []
    q = deque([root])
    while q:                                                # level order, right child first
        n = q.popleft(); stack.append(n)
        if n.right is not None: q.append(n.right)
        if n.left is not None: q.append(n.left)
    while stack: visit(stack.pop())                         # pop: deepest level, left to right

def morris_inorder(root):                     # inorder with no stack and no recursion
    cur = root
    while cur is not None:
        if cur.left is None:
            visit(cur); cur = cur.right; continue                        # nothing left of it
        pred = cur.left                                                  # inorder predecessor:
        while pred.right is not None and pred.right is not cur:          # rightmost on the left
            pred = pred.right
        if pred.right is None:
            pred.right = cur; cur = cur.left                             # thread it, then go left
        else:
            pred.right = None; visit(cur); cur = cur.right               # came back: unthread, visit

Tree Traversals, in JavaScript

function inorder(n) {
  if (n === null) return;
  inorder(n.left);
  visit(n);
  inorder(n.right);
}

function levelOrder(root) {
  const q = [root];
  while (q.length > 0) {
    const n = q.shift();
    visit(n);
    if (n.left !== null) q.push(n.left);
    if (n.right !== null) q.push(n.right);
  }
}

function zigzag(root) {                                 // level order, alternating direction
  let level = [root];
  let leftToRight = true;
  while (level.length > 0) {
    for (const n of leftToRight ? level : [...level].reverse()) visit(n);
    level = level.flatMap((n) => [n.left, n.right].filter((c) => c !== null));
    leftToRight = !leftToRight;
  }
}

function reverseLevelOrder(root) {                      // bottom level first
  const stack = [];
  const q = [root];
  while (q.length > 0) {                                // level order, right child first
    const n = q.shift();
    stack.push(n);
    if (n.right !== null) q.push(n.right);
    if (n.left !== null) q.push(n.left);
  }
  while (stack.length > 0) visit(stack.pop());          // pop: deepest level, left to right
}

function morrisInorder(root) {                // inorder with no stack and no recursion
  let cur = root;
  while (cur !== null) {
    if (cur.left === null) { visit(cur); cur = cur.right; continue; }   // nothing left of it
    let pred = cur.left;                                              // inorder predecessor:
    while (pred.right !== null && pred.right !== cur) pred = pred.right;   // rightmost on the left
    if (pred.right === null) { pred.right = cur; cur = cur.left; }    // thread it, then go left
    else { pred.right = null; visit(cur); cur = cur.right; }          // came back: unthread, visit
  }
}

Tree Traversals, in Kotlin

fun inorder(n: Node?) {
    if (n == null) return
    inorder(n.left)
    visit(n)
    inorder(n.right)
}

fun levelOrder(root: Node) {
    val q = ArrayDeque(listOf(root))
    while (q.isNotEmpty()) {
        val n = q.removeFirst()
        visit(n)
        n.left?.let { q.addLast(it) }
        n.right?.let { q.addLast(it) }
    }
}

fun zigzag(root: Node) {                                    // level order, alternating direction
    var level = listOf(root); var leftToRight = true
    while (level.isNotEmpty()) {
        for (n in if (leftToRight) level else level.reversed()) visit(n)
        level = level.flatMap { listOfNotNull(it.left, it.right) }
        leftToRight = !leftToRight
    }
}

fun reverseLevelOrder(root: Node) {                         // bottom level first
    val stack = ArrayDeque<Node>()
    val q = ArrayDeque(listOf(root))
    while (q.isNotEmpty()) {                                 // level order, right child first
        val n = q.removeFirst(); stack.addLast(n)
        n.right?.let { q.addLast(it) }; n.left?.let { q.addLast(it) }
    }
    while (stack.isNotEmpty()) visit(stack.removeLast())     // pop: deepest level, left to right
}

fun morrisInorder(root: Node?) {              // inorder with no stack and no recursion
    var cur = root
    while (cur != null) {
        if (cur.left == null) { visit(cur); cur = cur.right; continue }   // nothing left of it
        var pred = cur.left!!                                             // inorder predecessor:
        while (pred.right != null && pred.right !== cur) pred = pred.right!!   // rightmost on the left
        if (pred.right == null) { pred.right = cur; cur = cur.left }      // thread it, then go left
        else { pred.right = null; visit(cur); cur = cur.right }           // came back: unthread, visit
    }
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • Inorder on a search tree comes out sorted, which is the fastest way to check one is valid.
  • Pre, in and post differ only in where visit sits among the two recursive calls.
  • Level order is the odd one out: it needs a queue rather than the call stack. Morris needs neither, by threading each subtree's rightmost node back to its owner and removing it again.

Where this is used

AST visitors in Babel and ESLintCompilers

A plugin registers enter and exit handlers for a node type: enter fires on the way down, which is preorder, and exit fires on the way back up, which is postorder. A transform that rewrites a node out of its already-rewritten children has to run in exit, because at enter the children have not been touched yet. Picking the wrong hook is a common plugin bug.

du, rm -r and find -depthOperations

A directory's size is unknown until every child has been measured, so du has to report postorder. rm -r has the same shape for a different reason: a directory cannot be unlinked while it still holds entries. find walks preorder by default and offers -depth to switch to postorder, which is why -delete turns -depth on for you.

Layout in Flutter and browser enginesGraphics

Layout is two directions over one tree. Constraints travel down in preorder, sizes come back up in postorder because a column cannot know its own height until every child has reported one, and the parent then sets each child's position now that it knows the size. A single pass in either direction alone would not have the information it needs.

Garbage collector markingLanguage runtimes

A tracing collector walks the object graph to find what is still reachable, and it typically runs when memory is already tight, which is the worst moment to allocate a traversal stack. Pointer reversal, the Deutsch-Schorr-Waite scheme, takes Morris's bargain: it temporarily flips the pointer it arrived on so the object itself records the way back, then restores it on the way out. No stack that grows with the depth of the heap, and the pointers are left exactly as they were found.

Why it works this way

Why level order needs a queue when the other three do not

Pre, in and post only ever need to get back to an ancestor, and the call stack already holds that path for free. Level order needs the node to the right at the same depth, which is not an ancestor and sits nowhere on the current path, so nothing on the stack can supply it. The queue is the explicit store for nodes that have been seen but not yet visited, kept in the order they were seen.

Why reverse level order enqueues the right child first

A stack hands back whatever order it was filled in, reversed. Filling it top to bottom and left to right would pop bottom to top but right to left, which is not what you want. Pushing the right child first makes the queue emit each level right to left, and reversing that lands on the bottom level first, left to right.

The recursive space bound is O(h), and h can be n

On a balanced tree the recursion is about log n frames deep, which costs nothing. A tree built by inserting already-sorted keys is a single chain, so h equals n and the traversal needs one frame per node. A few tens of thousands of nodes is enough to overflow a default JVM thread stack, which is the real reason an explicit stack or Morris is worth knowing. The breadth-first walks do not have this bound at all: their queue holds a whole level, so their cost is the width of the tree, and on a balanced tree the widest level is about half the nodes.

Morris leaves the tree temporarily broken

While the walk is in progress, some right pointers point back up at an ancestor, so the structure is not a tree: a reader that follows one of those borrowed pointers is sent back to a node it has already passed and can loop forever. It also cannot be abandoned halfway, since breaking out of the loop early leaves those threads in place, and it will not run on a tree you are only allowed to read. Finding each predecessor walks the right spine of a left subtree, so some edges are crossed up to three times, but that is a constant factor and the total stays O(n).

Read more

Next up

BFS and DFS

Breadth-first from 0

Next lesson: BFS and DFS