Question

What are tree traversals?

Answer 1

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