Question

Respond to the following in a minimum of 175 words:

Explain two different ways to traverse a tree and how beneficial or not each tree traversing algorithm could be to an organization.

Answer 1

Ways to traverse a tree:

There are two methods to traverse a tree. The tree traversal means visiting each and every node of a tree.The two methods are:

• Depth first
• Breadth first

Depth first traversal:

The depth first traversal methods has three variants that are associated with it.They are as shown below.

• Inorder traversal
• Preorder traversal
• postorder traversal

These three variants can be briefly explained as shown below.

Inorder traversal:

The inorder traversal is the method in which the nodes of the tree are visited based on the key values in ascending order.This method of traversal is called as inorder traversal.

When we need to create the sorted list of node values of tree, we can use this inorder traversal algorithm to create the ascending order of values.

The sample algorithm that can be used to traverse a tree using inorder traversal method is shown below.

void inorder_traversal(node root)

{

if(root!=NULL)

{

inorder_traversal(root.left);

root.displayNode();

inorder_traversal(root.right);

}

}

Postorder traversal:

The post order traversal is the traversal method in which all the nodes of all subtrees are processed first, then the root node.

This is called as postorder traversal.

The sample algorithm that can be used to traverse a tree using postorder traversal method is shown below.

void postorder_traversal(node root)

{

if(root!=NULL)

{

postorder_traversal(root.left);

postorder_traversal(root.right);

root.displayNode();

}

}

Preorder traversal:

The preorder traversal is the method in which all the nodes of a tree are processed by processing the root node first, then the nodes of all the subtrees recursively.

This is called as preorder traversal.

This is exactly opposite to the postorder traversal.

The sample algorithm that can be used to traverse a tree using preorder traversal method is shown below.

void preorder_traversal(node root)

{

if(root!=NULL)

{

root.displayNode();

postorder_traversal(root.left);

postorder_traversal(root.right);  

}

}

These are the three variants of depth first traversal methods.

Breadth first traversal:

This method of traversal is also known as level order traversal.

In this method of traversal, we first access the root node,then the children of root node from left to right fashion.

This is called as breadth first traversal of a tree.