Data Structure : Tree traversal algorithm

We have discussed tree and binary tree in our last post part1 and part2. We discussed most common operations on Tree and Binary Tree. In this post we will discuss Tree traversal.

Traversing a tree mean visiting each node in specified order. Traversing is not as commonly used as find, insert and delete operations. It is not fast, but is very useful in some situation. There are three simple orders in which tree can be transferred: Inorder, Preorder and Postorder. We will discuss these traversing orders only.

Inorder Traversal

This is the most commonly used traversal order for Binary tree. An inorder traversal of binary tree will cause all the nodes to be visited in ascending order.  This is useful when you need to create a sorted list of data in a binary tree. Simplest way to execute traversal is through recursion. Below are the three steps to implement inorder traversal

1. Visit node’s left sub tree
2. Visit node
3. Visit node’s right sub tree

Jave code for inorder traversal is

private void inOrder(Node node)

{

if(node != null)

{

inOrder(node.leftChild);

System.out.print(node.getValue() + “ “);

inOrder(node.rightChild);

}

}

Preorder and Postorder Traversal

These are almost same as inorder traversal; only the sequence of traversing node, left subtree and right subtree is different. These are used generally in parsing and analysing expression like algebra expression.

Below are the steps to execute preorder traversal

1. Visit node
2. Visit node’s left sub tree
3. Visit node’s right sub tree

Java code for prorder traversal is

private void preOrder(Node node)

{

if(node != null)

{

System.out.print(node.getValue() + “ “);

preOrder(node.leftChild);

preOrder(node.rightChild);

}

}

Similarly, below are the steps to execute postorder traversal

1. Visit node’s left sub tree
2. Visit node’s right sub tree
3. Visit node

Java code for postorder traversal is

private void postOrder(Node node)

{

if(node != null)

{

postOrder(node.leftChild);

postOrder(node.rightChild);

System.out.print(node.getValue() + “ “);

}

}