## Saturday, January 03, 2009

### 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;
}
}