Chapter 2 - Tree Traversal: DFS, BFS

This chapter goes over ADT, linked list and tree, but we are going to focus on tree traversal algorithm such as DFS and BFS

Understanding DFS

Preorder:

def PreOrder(root):
    if not root:
        return 
    print(root.val)
    PreOrder(root.left)
    PreOrder(root.right)

Postorder:

def PostOrder(root):
    if not root:
        return
    PostOrder(root.left)
    PostOrder(root.right)
    print(root.val)

Inorder:

def InOrder(root):
    if not root:
        return
    PostOrder(root.left)
    print(root.val)
    PostOrder(root.right)

The difference between these orders is how we put the print statement or how we handle operations in general. This is a good explanation of them.

Applications on DFS

Suppose we have a tree, and each node has some value, what's the max accumulated value on a path from root to leaf?

max_value = float('inf')
def PreOrder(root, value):
    global max_value
    if not root:
        max_value = max(max_value, value)
        return 
    value += root.val
    PreOrder(root.left)
    PreOrder(root.right)   

• 112. Path Sum - My Solution

• 113. Path Sum II - My Solution

• 437. Path Sum III - My Solution

• 257. Binary Tree Paths - My Solution

• 105. Construct Binary Tree from Preorder and Inorder Traversal - My Solution

---

Understanding BFS

BFS does not have multiple process algorithms like DFS do because they are innately different. BFS focuses on level-order rather than reaching the deepest node. This is a simple BFS:

def BFS(root):
    queue = deque() # initalize a queue
    queue.append(root)
    result = []
    while queue:
        current = queue.popleft()
        result.append(current.val)
        
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)
    return result
        

What this code does is that it initialize a queue, appends the root of the tree into the queue, and starts processing its children by adding them to the queue.

• 102. Binary Tree Level Order Traversal - My Solution

• 107. Binary Tree Level Order Traversal II - My Solution

• 103. Binary Tree Zigzag Level Order Traversal - My Solution