Choosing a Traversal

Each question below describes a task on a binary tree. Pick one of the four traversals for it: pre-order, in-order, post-order, or level-order.

Here is a binary tree that stores an arithmetic expression, with an operator at each internal node and a number at each leaf:

          ╭───╮
          │ * │
          ╰─┬─╯
     ┌──────┴──────┐
   ╭─┴─╮         ╭─┴─╮
   │ + │         │ - │
   ╰─┬─╯         ╰─┬─╯
  ┌──┴──┐       ┌──┴──┐
╭─┴─╮ ╭─┴─╮   ╭─┴─╮ ╭─┴─╮
│ 3 │ │ 4 │   │ 9 │ │ 1 │
╰───╯ ╰───╯   ╰───╯ ╰───╯

Solution

Post-order. An operator can only be applied once both of its operands have been computed.

Solution

Pre-order. A node’s copy must exist before the copies of its children can be attached to it.

Solution

Level-order. It visits every node at one depth before any deeper node, so the first negative value it reaches is the closest to the root.

Solution

In-order. It prints a node’s entire left subtree before the node and its entire right subtree after it, which puts every node after the smaller values and before the larger ones.