How does Preorder Traversal of Binary Tree work?

Consider the following tree:

If we perform a preorder traversal in this binary tree, then the traversal will be as follows:

Step 1: At first the root will be visited, i.e. node 1.

Node 1 is visited

Step 2: After this, traverse in the left subtree. Now the root of the left subtree is visited i.e., node 2 is visited.

Node 2 is visited

Step 3: Again the left subtree of node 2 is traversed and the root of that subtree i.e., node 4 is visited.

Node 4 is visited

Step 4: There is no subtree of 4 and the left subtree of node 2 is visited. So now the right subtree of node 2 will be traversed and the root of that subtree i.e., node 5 will be visited.

Node 5 is visited

Step 5: The left subtree of node 1 is visited. So now the right subtree of node 1 will be traversed and the root node i.e., node 3 is visited.

Node 3 is visited

Step 6: Node 3 has no left subtree. So the right subtree will be traversed and the root of the subtree i.e., node 6 will be visited. After that there is no node that is not yet traversed. So the traversal ends.

The complete tree is visited

So the order of traversal of nodes is 1 -> 2 -> 4 -> 5 -> 3 -> 6.

Preorder traversal is defined as a type of tree traversal that follows the Root-Left-Right policy where:

• The root node of the subtree is visited first.
• Then the left subtree  is traversed.
• At last, the right subtree is traversed.