binary traversal: preorder, postorder, and inorder

2021-11-12

~3 min read

533 words

There are three standard ways to traverse a binary tree when traversing depth first:

Inorder (left, root, right)
Preorder (root, left, right)
Postorder (left, right, root)

Let’s imagine we have a tree comprised of nodes:

interface Node {
  val: number
  left: Node
  right: Node
}

How would we traverse these in our various orders?

Recursive

inorderTraversal.ts

function inorderTraversal(root: Node): number[] {
  return visitNode(root)
}

function visitNode(node: Node, values: number[] = []): number[] {
  if (!node) {
    return []
  }
  if (node.left) {
    visitNode(node.left, values)
  }
  if (node) {
    values.push(node.val)
  }
  if (node.right) {
    visitNode(node.right, values)
  }
  return values
}

This simple recursive approach means that we bias toward our left and keep visiting nodes all the way down until we reach a leaf.

Once there, we no longer have left nodes to visit, so we add the current node to the list of values. Then, we explore to the right.

Finally, if there’s no where to go, we return the array, so that we can continue one level up the tree.

Modifying it for preorder and postorder is as simple as rearranging the if statements:

preorderTraversal.ts

function preorderTraversal(root: Node): number[] {
  return visitNode(root)
}

function visitNode(node: Node, values: number[] = []): number[] {
  if (!node) {
    return []
  }
  if (node) {
    values.push(node.val)
  }
  if (node.left) {
    visitNode(node.left, values)
  }
  if (node.right) {
    visitNode(node.right, values)
  }
  return values
}

postorderTraversal.ts

function postorderTraversal(root: Node): number[] {
  return visitNode(root)
}

function visitNode(node: Node, values: number[] = []): number[] {
  if (!node) {
    return []
  }
  if (node.left) {
    visitNode(node.left, values)
  }
  if (node.right) {
    visitNode(node.right, values)
  }
  if (node) {
    values.push(node.val)
  }
  return values
}

Iteratively

What about doing this iteratively?

inorderIterative.ts

var inorderTraversal = function (root) {
  const result = []
  const stack = []
  let cur = root

  while (cur || stack.length !== 0) {
    // traverse the left side initially;
    // later, we will be adding the right side
    // but always with a bias toward the left
    while (cur) {
      stack.push(cur)
      cur = cur.left
    }
    // begin working our way through the left
    cur = stack.pop()
    result.push(cur.val)
    cur = cur.right
  }
  return result
}

Here, we make use of a stack to keep adding elements to our list and processing them one in turn.

The inner while loop means for each node, we push all of our left nodes to the top of the stack first.

Only after we’ve processed those, are we able to process the original node, and which point, the whole process starts over again since we add a right node and then may have new left nodes to process.

preorderIterativeTraversal.ts

var preorderIterativeTraversal = function (root) {
  const result = []
  const stack = []
  let cur = root

  while (cur || stack.length !== 0) {
    result.push(cur.val)
    cur.right && stack.push(cur.right)
    cur.left && stack.push(cur.left)
    cur = stack.pop()
  }
  return result
}

Preorder is even simpler. We can eliminate the internal loop.

Postorder, however, is not. For now, I’m going to leave this as a challenge for another day and use my recursive approach if I need to process a binary tree in postorder.

postorderIterativeTraversal.ts

// TODO

Hi there and thanks for reading! My name's Stephen. I live in Chicago with my wife, Kate, and dog, Finn. Want more? See about and get in touch!