Write a Python source code to implement the Depth-First-Search algorithm for the following tree in Figure 2, where 5 is the root node. The output of the source code should be the order of the nodes visited in the graph. Implement the dfs() function. When a node has two children, visit the left child first then the right child.
Write a Python source code to implement the Depth-First-Search
following tree in Figure 2, where 5 is the root node. The output of the source code should be the
order of the nodes visited in the graph. Implement the dfs() function. When a node has two children, visit the left child first then the right child.
Use this Template:
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
# Traverse a tree DFS style.
def traverse(root):
# List that represents visited order.
ret = []
def dfs(node):
# TODO: Implement DFS algorithm here
return
dfs(root)
return ret
def main():
nodes = [None] * 9
for i in range(9):
nodes[i] = TreeNode(i+1)
# Tree construction
# 5
nodes[4].left = nodes[3]
nodes[4].right = nodes[5]
# 4
nodes[3].left = nodes[1]
# 2
nodes[1].left = nodes[0]
nodes[1].right = nodes[2]
# 6
nodes[5].right = nodes[7]
# 8
nodes[7].left = nodes[6]
nodes[7].right = nodes[8]
root = nodes[4]
print(traverse(root))
if __name__ == "__main__":
main()
Step by step
Solved in 2 steps with 1 images
