Tree Traversals

A company stores its org chart as a tree. Three people ask you for three different things. HR wants the chart printed as an indented list, each manager above their team. Finance wants the total salary of every team, which means you need each sub-team's total before you can add up the team above it. The CEO wants a list of who reports at each level: herself, then her direct reports, then theirs.

Same tree, three different orders of visiting the people in it. Visiting every node in a fixed order is called a traversal. In many tree problems, picking the right order is most of the work.

#Depth first: three moments to visit a node

In Binary Trees you saw the pattern: handle the empty tree, recurse into the left child, recurse into the right child. That walk goes deep down one branch before it comes back, so it is called depth-first. It touches every node at three moments: on the way down, between its two children, and on the way back up.

"Visiting" a node means doing your real work there: printing it, adding it to a list, comparing it. The only question is at which of the three moments you do it.

• Preorder: visit the node, then its left subtree, then its right subtree. Parents come before their children. That is the HR outline.
• Inorder: left subtree, then the node, then the right subtree.
• Postorder: left subtree, then right subtree, then the node. Children come before their parents. That is the Finance totals.

#Inorder, traced

Here is inorder on a six-node tree. The "calls" row is the call stack: every call that has started and not yet finished. A node cannot be visited until its whole left subtree is done.

inorder(node):  if node is empty: return  inorder(node.left)  visit(node)  inorder(node.right)

That sorted output is no accident. This tree is a binary search tree, where everything left of a node is smaller and everything right is bigger. On any other tree, inorder just gives "left side, me, right side". For the same tree, the three depth-first orders are:

#The code

The three functions are identical except for where one line sits.

function preorder(node, out = []) {
  if (node === null) return out;
  out.push(node.val);         // visit, then the children
  preorder(node.left, out);
  preorder(node.right, out);
  return out;
}
 
function inorder(node, out = []) {
  if (node === null) return out;
  inorder(node.left, out);
  out.push(node.val);         // visit between the children
  inorder(node.right, out);
  return out;
}
 
function postorder(node, out = []) {
  if (node === null) return out;
  postorder(node.left, out);
  postorder(node.right, out);
  out.push(node.val);         // visit after the children
  return out;
}

def preorder(node, out=None):
    if out is None:
        out = []
    if node is not None:
        out.append(node.val)     # visit, then the children
        preorder(node.left, out)
        preorder(node.right, out)
    return out
 
def inorder(node, out=None):
    if out is None:
        out = []
    if node is not None:
        inorder(node.left, out)
        out.append(node.val)     # visit between the children
        inorder(node.right, out)
    return out
 
def postorder(node, out=None):
    if out is None:
        out = []
    if node is not None:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.val)     # visit after the children
    return out

#Without recursion

Recursion uses the call stack for you. On a very deep tree that stack can overflow, so you keep your own stack instead. For preorder it is short: pop a node, visit it, push its children. Push the right child first, so the left one is on top and comes out first.

function preorderIterative(root) {
  const out = [];
  const stack = root === null ? [] : [root];
  while (stack.length > 0) {
    const node = stack.pop();
    out.push(node.val);
    // push right first so that left is popped first
    if (node.right !== null) stack.push(node.right);
    if (node.left !== null) stack.push(node.left);
  }
  return out;
}

def preorder_iterative(root):
    out = []
    stack = [] if root is None else [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        # push right first so that left is popped first
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
    return out

#Breadth first: level by level

The CEO's request does not fit any depth-first order. She wants everyone at depth 0, then everyone at depth 1, and so on. This is level-order traversal, also called breadth-first.

The idea: keep a list of the nodes on the current level. Record their values. Then build the next level from their children, left to right. Repeat until a level comes out empty.

level = [root]while level is not empty:  record the values in level  next = children of level, left to right  level = next

function levelOrder(root) {
  const levels = [];
  let level = root === null ? [] : [root];
  while (level.length > 0) {
    levels.push(level.map((node) => node.val));
    const next = [];
    for (const node of level) {
      if (node.left !== null) next.push(node.left);
      if (node.right !== null) next.push(node.right);
    }
    level = next;
  }
  return levels;
}
// [[8], [3, 10], [1, 6, 14]]

def level_order(root):
    levels = []
    level = [] if root is None else [root]
    while level:
        levels.append([node.val for node in level])
        next_level = []
        for node in level:
            if node.left is not None:
                next_level.append(node.left)
            if node.right is not None:
                next_level.append(node.right)
        level = next_level
    return levels
# [[8], [3, 10], [1, 6, 14]]

This is breadth-first search on a tree. The usual way to write it is with a single queue: take from the front, add children at the back. Swapping two lists does the same thing and keeps the levels apart for free. Breadth-First Search uses the queue form on graphs.

#Cost

Both kinds touch each node a constant number of times. They differ in memory: depth-first remembers one path, breadth-first remembers one whole level. On a wide, shallow tree, depth-first is lighter. On a long, thin one, breadth-first is.

#Common mistakes

#Check yourself

#What to practise next

The sorted inorder output hinted at something bigger. Binary Search Trees arrange values so you can find, add and remove one without visiting the whole tree.