Traversing binary trees

What are trees? Trees are data structures which contain a node and one or more children. A binary tree is a tree in which each node is either empty or contains at max two children.

A binary tree...

root --------> R
                /    \
               L     R
              /  \   /  \
             l  r   rl  

A binary tree of height h<=0 has at max 2^h+1 - 1 nodes. And the height of the tree h = log2(n), where n is the number of nodes in the binary tree.

Lets check out the recursive functions used to traverse the binary trees:

1. Preorder traversal:
Preorder traversal does the following recursively :
-> visit the root
-> traverse left subtree
-> traverse right subtree

function preorder(tree)
{
  if (tree == null) return;

  print(tree.root);
  call preorder(tree.left_subtree);
  call preorder(tree.right_subtree);
}

2. Inorder traversal:
Inorder traversal does the following recursively :
-> traverse left subtree
-> visit the root
-> traverse right subtree

function inorder(tree)
{
  if (tree == null) return;

  call inorder(tree.left_subtree);
  print(tree.root);
  call inorder(tree.right_subtree);
}

3. Postorder traversal:
Postorder traversal does the following recursively :
-> traverse left subtree
-> traverse right subtree
-> visit the root

function postorder(tree)
{
  if (tree == null) return;

  call postorder(tree.left_subtree);
  call postorder(tree.right_subtree);
  print(tree.root);
}

4. Breadth-first or level-order traversal:
In Level-order traversal each level is visited successively starting from root(level-0) and nodes are visited from left to right on each level. This is generally implemented using a queue data structure.

- push the root node in the queue
- pop the node from the queue, push the left and right child node in the queue.
- pop the root->left node from the queue and push the left and right child node of root->left in the queue.
- pop the root->right node from the queue and push the left and right child node of root->right in the queue.

function levelorder(tree)
{
  queue.push(tree.root);
  while(queue.size > 0)
  {
    Node n = queue.pop(); //get first node in queue
    if (n.left != null) queue.push(n.left);
    if (n.right != null) queue.push(n.right);
    print n;
  }
}