What are tree traversals?

Web Development
,
#1

Tree traversal is a process of visiting all the nodes of a tree. Since 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 −
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.
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.
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]
#2

Traversal is simply a way to step over each node in the tree in turn (usually performing an action on it like displaying it). Note, I’m not going to talk about stuff like graphs (yet) … I think you should understand trees before you understand graphs (many of it is the same and you may just confuse yourself if you try to go at all of it at once, but you can take note that traversals also apply to graphs).

The need for it? Well, trees are usually used as an efficient way to store data in some sort of order (perhaps something like alphabetically, or maybe to show some structure behind the data like the object hierarchy in an HTML file). When you want to display or calculate stuff in that order you need to step through the tree. And thus, rather that re-writing the code each time to step from one node to another, you write a traversal function so yo can just call it and do the specific action you wanted on each node in turn.

Think of traversals as the same principle you use to iterate over an array, or enumerate any other collection. In fact you could call the other stuff traversals too, it’s just that deciding which node in the collection to “traverse” over next is a lot more trivial than doing so in a tree. Thus generally traversals refer to trees, while for other collections they’re called iterations or enumerations.