Binary Tree Traversals

Tree traversals visit each node in a tree and perform some action. We will call the action "visit", it could be checking if the node is a leaf, checking the nodes's value, etc. We look at binary tree traversals. The traversals are easily extended to general trees.

Since a tree is a recursive structure useful tree traversals may be written recursively. For a recursive traversal of a binary tree, when at a node there are three things that can be done: visit, traverse the left subtree, and traverse the right subtree. Varying the order we have three important binary tree traversals:

  1. preorder - visit, traverse left, traverse right
  2. postorder - traverse left, traverse right, visit
  3. inorder - traverse left, visit, traverse right

Drawing a path that starts at the root and goes in a counter-clockwise direction past each node is helpful.

Preorder

preorder(Node)
{
   if (Node != null)
   {
       visit Node
       preorder(left_child)
       preorder(right_child)
   }
}

Postorder

postorder(Node)
{
   if (Node != null)
   {
       postorder(left_child)
       postorder(right_child)
       visit Node
   }
}

Inorder

inorder(Node)
{
   if (Node != null)
   {
       inorder(left_child)
       visit Node
       inorder(right_child)
   }
}

Another search visits all nodes level-by-level. It is iterative and uses a queue.

Level-order

level_order(root)
{
   q.push(root)

   while ( ! q.empty() )
   {
       Node = q.pop()
       visit Node
       q.push(left_child)
       q.push(right_child)
   }
   
}

List the nodes of the binary tree below in the above orders. 

              A
            /   \
          /       \
         D         G 
       /   \      /  \
      H     K    M    C
     /     /    / \
    W     R    X   T
   / \
  E   S
preorder A D H W E S K R G M X T C
postorder E S W H R K D X T M C G A
inorder E W S H D R K A X M T G C
level order A D G H K M C W R X T E S

Traversal Use

Leaf Count

void (Node, int & count)    // count leaves, preorder traversal
    if ( Node != null )
        if ( left_child == null && right_child == null )
            ++ count
        leafCount(left_child, count)
        leafCount(right_child, count)

Depth of Tree

int depth(Node)             // find greatest depth, postorder traversal
    if ( Node == null )
        depthval = -1
    else
        depthLeft  = depth(left_child)
        depthRight = depth(right_child)
        depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight)
    return depthval