This content originally appeared on DEV Community and was authored by Rahul kumar
There are two different way to traverse Binary Search Tree and Graph. The first approach is Breadth First Search (BFS) and the second one is Depth First Search (DFS). Both approaches have their own use case but two common objectives one can think of are finding the shortest distance between two nodes and detecting the loop in a tree.
BFS traverse horizontally acrross all levels, while DFS traverse vertically. Since we are traversing vertically, it give us more flexibility in choosing our approach of travelling.
These 3 paths are Pre-order, In-order, and Post-order. Although this flexibility is useful, it can also be confusing. Suppose you forget the order of DFS traversals but remember the rest of the code during an exam or interview. This could be disastrous because the overall code for DFS is relatively straightforward and similar for all three cases.
Depth First Search Traversal Approaches
In today's tutorial we are looking into the easiest way possible to remember DFS traversals.
- DFS Pre-Order: In Pre-order DFS we move from Root/Subroots node to the Left node and to the Right node.
- DFS In-Order: In In-order DFS we move from Left node to Root/Subroots node and to the Right node.
- DFS Post-Order: In Post-order DFS we move from Left node to Right node and then to Root/Subroots node.
Probing the DFS Traversal Approaches to make it Easy to Remember
There are two common things in all three of the statements.
- The order of Root/Subroot is changing but Left and Right are constant in simple words, we first move left and then right in all 3 traversals.
- The traversal method's name indicate the position of Root/Subroot traversal.
Now let's see this through an example.
We have this BST
DFS Pre-Order
We first do the DFS Pre-order for this bst:
def dfs_in_order():
results = []
def traverse(current_node):
results.append(current_node)
if current_node.left:
traverse(current_node.left)
if current_node.right:
traverse(current_node.right)
traverse(root)
return results
In above code we are adding Root first than traversing left and right if they exist. The output will be [47,21,18,27,76,52,82]
Notice our Root/Subroots is before Left and Right.
DFS In-Order
Doing DFS In-order will give us this result: [18,21,27,47,52,76,82]
Notice our Root/Subroots is in between Left and Right node.
def traverse(current_node):
if current_node.left:
traverse(current_node.left)
results.append(current_node)
if current_node.right:
traverse(current_node.right)
DFS Post-Order
Now we have left with DFS Post-order.
def traverse(current_node):
if current_node.left:
traverse(current_node.left)
if current_node.right:
traverse(current_node.right)
results.append(current_node)
Post-order wil further push results.append() to bottom. The output generated will be [18,27,21,52,82,76,47].
Notice how our Root/Subroots are after Left and Right node.
Conclusion:
Using "In/Pre/Post" prefix will help you determine the position of Root and Subroots in DFS easily. Other than that we are traversing Left to Right in all cases regardless of the position of Root and Subroots.
This content originally appeared on DEV Community and was authored by Rahul kumar
Rahul kumar | Sciencx (2024-06-19T15:19:03+00:00) DFS Traversal Guide: Easy way to remember DFS Traversel Path. Retrieved from https://www.scien.cx/2024/06/19/dfs-traversal-guide-easy-way-to-remember-dfs-traversel-path/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.