A tree consisting of n nodes is given, we need to print its DFS.
Input : Edges of graph 1 2 1 3 2 4 3 5 Output : 1 2 4 3 5
A simple solution is to do implement standard DFS.
We can modify our approach to avoid extra space for visited nodes. Instead of using the visited array, we can keep track of parent. We traverse all adjacent nodes but the parent.
Below is the implementation :
# Python3 code to perform DFS of given tree :
# DFS on tree
def dfs(List, node, arrival):
# Printing traversed node
# Traversing adjacent edges
for i in range(len(List[node])):
# Not traversing the parent node
if (List[node][i] != arrival):
dfs(List, List[node][i], node)
# Driver Code
if __name__ == ‘__main__’:
# Number of nodes
nodes = 5
# Adjacency List
List = [ for i in range(10000)]
# Designing the tree
# Function call
dfs(List, 1, 0)
# This code is contributed by PranchalK
1 2 4 3 5
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.