1.

What are tree traversals?

Answer»

Tree traversal is the process of visiting all the nodes of a tree. Since the root (head) is the first node and all nodes are connected via edges (or links) we always start with that node. There are three ways which we use to traverse a tree −

1. Inorder Traversal:


  • Algorithm:

    • Step 1. Traverse the left subtree, i.e., call Inorder(root.left)

    • Step 2. Visit the root.

    • Step 3. Traverse the right subtree, i.e., call Inorder(root.right)



  • Inorder traversal in Java:

// Print inorder traversal of given tree.
void printInorderTraversal(Node root)
{
if (root == null)
return;
//first traverse to the left subtree
printInorderTraversal(root.left);
//then print the data of node
System.out.print(root.data + " ");
//then traverse to the right subtree
printInorderTraversal(root.right);
}
  • Uses: In binary search trees (BST), inorder traversal gives nodes in ascending order.

2. Preorder Traversal:


  • Algorithm:

    • Step 1. Visit the root.

    • Step 2. Traverse the left subtree, i.e., call Preorder(root.left)

    • Step 3. Traverse the right subtree, i.e., call Preorder(root.right)



  • Preorder traversal in Java:

// Print preorder traversal of given tree.
void printPreorderTraversal(Node root) 
{ 
if (root == null) 
return; 
//first print the data of node
System.out.print(root.data + " ");
//then traverse to the left subtree
printPreorderTraversal(root.left);
//then traverse to the right subtree
printPreorderTraversal(root.right); 
}
  • Uses:

    • Preorder traversal is commonly used to create a copy of the tree.

    • It is also used to get prefix expression of an expression tree.


3. Postorder Traversal:


  • Algorithm:

    • Step 1. Traverse the left subtree, i.e., call Postorder(root.left)

    • Step 2. Traverse the right subtree, i.e., call Postorder(root.right)

    • Step 3. Visit the root.



  • Postorder traversal in Java:

// Print postorder traversal of given tree.
void printPostorderTraversal(Node root) 
{ 
if (root == null) 
return;
//first traverse to the left subtree
printPostorderTraversal(root.left);
//then traverse to the right subtree
printPostorderTraversal(root.right);
//then print the data of node
System.out.print(root.data + " ");
}
  • Uses:

    • Postorder traversal is commonly used to delete the tree.

    • It is also useful to get the postfix expression of an expression tree.


Consider the following tree as an example, then:


  • Inorder Traversal => Left, Root, Right : [4, 2, 5, 1, 3]

  • Preorder Traversal => Root, Left, Right : [1, 2, 4, 5, 3]

  • Postorder Traversal => Left, Right, Root : [4, 5, 2, 3, 1]


Discussion

No Comment Found

Related InterviewSolutions