Binary Tree- Depth First Search(DFS) Traversal explained
This is traversal by travelling as deep as possible on one path from the root node to the leaf node before traversing the next path(backtracking). Unlike breadth first search (BFS),it’s easier to implement DFS by use of recursion and requires less memory than BFS as well.
Types of Depth First Search traversals
There are 3 variations of DFS
- Inorder traversal -Left,Root,Right
- Preorder traversal-Root,Left,Right
- Postorder traversal-Left,Right,Root
Inorder Traversal
-In this approach, start at the left subtree to the leftmost leaf node, then its root, its right sibling and backtrack all way up to the tree root. Then move to the right subtree and move to the left most leaf node in the right subtree, its root ,then its right sibling if any until all nodes in the right subtree have been visited in this fashion.
Example 1
In the tree below,each node will be printed out in inorder traversal fashion.
InOrder traversal output for the above is: 58 60 65 68 70 80 82 85
Explanation:
The left most node 58 is the first to be visited and printed out. The next node to be visited is 58’s parent, 60. Since 60 has no right child, visitation backtracks to 60’s parent 65.65 is then printed and its right child 68 is visited and printed out. Traversal returns to the root 70 since 68 is a leaf node. From here visitation moves to the right subtree and goes to the most left node again in this case 80.80 is a leaf node so traversal backtracks to its parent 82.82’s right child 85 is then visited and printed out. Traversal ends.
Preorder Traversal
Preorder traversal starts at the tree root, followed by the left node and then the right node. That traversal fashion first happens to the left subtree first before moving to the right subtree.
Using below tree (same tree used in Example 1) above, we have output as demonstrated below.
Example 2
Preorder traversal Output: 70 65 60 58 68 82 80 85
Explanation:
The root of the tree,70 is first to be visited and printed. Next 70’s left child 65 is visited and printed.65’s left child 60 is visited and printed.60’s left child 58 is visited and printed.58 is a leaf node, so flow backtracks to 60.60 has no right child so flow backtracks to 65.65 has an unvisited right child 68.68 is then visited and printed. Flow now backtracks to 65’s parent 70, which is also the tree root.70 was visited earlier and now its time to visit the right subtree.70’s right child 82 is visited and printed.82’s left child 80 is visited and printed.80 is a leaf node, so visitation backtracks to its parent 82.82’s right child 85 is visited and printed. At this point the tree is full traversed in preorder fashion.
Postorder Traversal
In this fashion, the Left most leaf node is visited first, followed by its right side sibling if any then lastly its parent. Backtracking moves to the preceding parent node, its right child if any, the right child’s subtree if any and backtracks all the way to the immediate left child of the tree’s root. Traversal then moves to the right child of the tree’s root whereby the left most leaf node of the right subtree is traversed, followed its right sibling if any and then their parent. This process repeats in the left child-right sibling and their parent until eventually the tree’s root node is visited at last.
Let’s look at below example using the tree we have used in example 1 and example 2
Example 3
Output: 58 60 68 65 80 85 82 70
Explanation:
The left most node 58 is visited and printed. It has no right hand sibling so flow returns to its parent 60 which is visited and printed.60 has a right side sibling 68 which is visited and printed after which its parent 65 is visited and printed.65 has a right sibling 82.82 is the top most node in the right subtree. Its not visited first as we have a left most node 80 in the right subtree.80 is then visited and printed.80 has a right side sibling 85 which is visited and printed. Flow returns to their parent 82 which is then visited and printed. Finally the parent to 82,70 which is also the tree root is then visited and printed.
