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()
![Figure 2
2
4
(3
5
8
(9](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F02c99683-a01b-4e64-96f8-7137fedec6c4%2F34b60503-5f20-4086-90d0-782b5c3ed0ae%2Fpzhv32_processed.png&w=3840&q=75)
![](/static/compass_v2/shared-icons/check-mark.png)
Step by step
Solved in 2 steps with 1 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)