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.
Step 2: After this, traverse in the left subtree. Now the root of the left subtree is visited i.e., 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.
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.
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.
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.
So the order of traversal of nodes is 1 -> 2 -> 4 -> 5 -> 3 -> 6.
Preorder Traversal of Binary Tree
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.