Understand Tree Pre-order Traversal in Java2 min read

There are a number of ways let us traverse a tree. Recall that tree traversal is the process of visiting all nodes in a tree only once. Unlike an in-order traversal, pre-order traversal of a tree can process as follow:

  • Visit the root of the tree
  • Explore and visit all the node in the left subtree
  • Explore and visit all the node in the right subtree
Pre-order traversal in a binary tree
visit(root);
preOrder(root.left);
preOrder(root.right);

If we take the image above as our example, the output will process as follow:

7 -> 2 -> 6 -> 3 -> 9 -> 14

As you can see, here we have 7 as our root node and this node will be visited first, then we recursively traverse the left subtree, finds a new root node with the key of 2, visit this node and explore its child, 6. After the left subtree is completely visited, we move to the right subtree and apply the same recursive manner.

Now, let’s construct a recursive pre-order traversal in Java:

private void preOrder(Node node) {
      if(node == null){ // if node is equal null, returns nothing
          return; 
      }
      System.out.println("Currently visit the node: " + node.element); // visit the current root node
      preOrder(node.left); // recursively visits the left subtree
      preOrder(node.right); // recursively visits the right subtree

  }

As we notice in the pre-order traversal, the root node always is visited first before any recursion, after visiting a root node this algorithm processes the left then the right subtree, the same rule is also applied with n-ary tree:

Pre-order in n-ary tree
3 -> 5 -> 8 -> 7 -> 6

Before we test this algorithm, let’s define a public preOrderTraversal() method which accepts no parameter:

public void preOrderTraversal() { 
    inOrder(root);
} 

In this public method, we just simply call the preOrder function and pass in the root which is an instance variable we already defined in the class. Now, let’s test this program:

 public static void main(String[] args){
    BST tree = new BST();
    tree.add(7);
    tree.add(2);
    tree.add(6);
    tree.add(3);
    tree.add(9);
    tree.add(14);
    tree.preOrderTraversal();
}

Output:

Currently visit the node: 7
Currently visit the node: 2
Currently visit the node: 6
Currently visit the node: 3
Currently visit the node: 9
Currently visit the node: 14

The complete code of the pre-order traversal can be found here.

In-order traversal can have many applications, it is topologically sorted, which means the parent is always processed before any of its child nodes. This property can be applied for scheduling a sequence of jobs or tasks.

Previous Article

Sign up for newsletter

* indicates required

Categories

Archives