Tree traversals

Preparing for interviews always go through different tree traversals. Wikipedia has an excellent article over tree traversal.



The tree traversals are:
> InOrder (Sorted Output)
> PreOrder (Root first)
> PostOrder [Depth First Search](children first)
> LevelOrder(Top Level First)

InOrder Code:

void InOrder(Node root){
if(root.left != null) InOrder(root.left);
print (root.value);
if(root.right != null) InOrder(root.right);
}


PreOrder Code:

void PreOrder(Node root){
print(root.value);
if(root.left != null) PreOrder(root.left);
if(root.right != null) PreOrder(root.right);
}


PostOrder Code (Depth First Search):

void PostOrder(Node root){
if(root.left != null) PostOrder(root.left);
if(root.right != null) PosOrder(root.right);
print(root.value);
}


LevelOrder Code :

void LevelOrder(Node root){
// use queue to get level order traversal
// Queue provides two functions. 1. head() 2.add()
Queue q = new Queue();
q.add(root);

while(!q.isEmpty()){
root = q.head();

if(root.left != null) q.add(root.left);
if(root.right != null) q.add(root.right)l

print(roor.value);

}
}


Except Level Order Traversal remaining of the traversal methods can be rewritten using stacks. Remember you might need to push and pop elements in stack rather than calling the function again. Also sometimes visited flag is required to make sure function is not repeating the same values again.

Have a great fight !!