Searching - Tree DFS/BFS

[ahasusie]

Tree problems:

1. can be solved by DFS
2. can be solved by BFS

DFS way:

1. divide and conquer
2. traversal

DFS way solutions:

1. iteration
2. recursion: (only need to remember how to recursion preorder/postorder traversal) 1). top down (preorder)
   2). buttom up (postorder / reversed preorder)

BFS way: traversal search

BFS way solutions: iteration

---

notes:

# at anytime if need to keep a global variable, use class
class Solution(object):
    def foo(self, root):
        self.globalVariable= 0      # usually it's the return value, the value we want
        self.dfs(root, 1)                 # dfs() function do sth to calculate the globalVariable, update
        return self.globalVariable # get the result, return it
    def dfs(self, node, depth):
        self.dfs(node.left)
        self.dfs(node.right)
        # do sth here, key part

[ahasusie]

traversal can be resolved by DFS and BFS. DFS: preorder/postorder/inorder BFS: levelorder

1/ when you delete nodes in a tree, deletion process will be in post-order 2/ post-order is widely use in mathematical expression, handle the expression using a stack. Each time when you meet a operator, you can just pop 2 elements from the stack, calculate the result and push the result back into the stack. 3/ for binary search tree, we can retrieve all the data in sorted order using in-order traversal. 4/ iteration preorder traversal, stack first append node.right then append node.left

[ahasusie]

DFS recursion and 2 implementions

---

top-down considered as kind of preorder traversal

1. return if root is null
2. if root is a leaf node:
3.      answer = max(answer, depth)         // update the answer if needed
4. maximum_depth(root.left, depth + 1)      // call the function recursively for left child
5. maximum_depth(root.right, depth + 1)     // call the function recursively for right child

class Solutions(object):
    def maxDepth(self, root):
        self.max_depth = 0
        self.dfs(root, 1)
        return self.max_depth

    def dfs(self, root, depth):
        if not root:
            return 0
        self.max_depth = max(depth, self.max_depth)
        self.dfs(root.left, depth+1)
        self.dfs(root.right, depth+1)

---

buttom-up regarded as kind of postorder traversal

1. return specific value for null node
2. left_ans = bottom_up(root.left)          // call function recursively for left child
3. right_ans = bottom_up(root.right)        // call function recursively for right child
4. return answers                           // answer <- left_ans, right_ans, root.val

def maxDepth(root):
    if not root:
        return 0
    l = maxDepth(root.left)
    r = maxDepth(root.right)
    return max(l, r)+1

# 104
# bfs iteration
# dfs iteration 
# dfs recursion traversal 
# dfs recursion divide and conquer
def maxDepth(root):
    # bfs iteration, top-down
    if not root:
        return 
    depth = 0
    q = deque()
    q.append([root, 1])
    while q:
        node, curDepth = q.popleft()
        if node:
            depth = max(depth, curDepth)
            if node.left:
                q.append([node.left, curDepth+1]) 
            if node.right:
                q.append([node.right, curDepth+1])            
    return depth

    # dfs iteration, top-down, preorder
    if not root:
        return
    depth = 0
    stack = [(root, 1)]
    while stack:
        node, curDepth = stack.pop()
        if node:
            depth = max(depth, curDepth)
            if node.right:
                stack.append((node.right, curDepth+1))
            if node.left:
                stack.append((node.left, curDepth+1))
    return depth

    # dfs recursion, divide and conquer, post order, buttom-up
    max depth = left/right subtree max depth + 1
    if not root:
        return 0
    return max(maxDepth(root.left), maxDepth(root.right)) + 1

# dfs recursion, traversal, top-down
class Solutions(object):
    def maxDepth(self, root):
        self.max_depth = 0
        self.dfs(root, 1)
        return self.max_depth

    def dfs(self, root, depth):
        if not root:
            return 0
        self.max_depth = max(depth, self.max_depth)
        self.dfs(root.left, depth+1)
        self.dfs(root.right, depth+1)

[ahasusie]

DFS 226, 104, 110, 257

# recursion dfs: 
def dfs(root):
    if not root: return 

# if depth involved:
def dfs(root):
    if not root: return 0

[ahasusie]

BFS use queue

• do level-order traversal in a tree.
• traverse a graph to search a path, especially the shortest path, from a start node to a target node.
• to traverse all the possible statuses. In this case, we can regard the statuses as the nodes in the graph while the legal transition paths as the edges in the graph.

1. BFS traversal in Tree (LC102) https://github.com/ahasusie/practiceCode/blob/master/bfs.py
2. BFS operation in graph (LC207, LC127, LC743) https://github.com/ahasusie/practiceCode/blob/master/graph.py
3. find the shortest path from the root to the target node()
4. max/min depth (513, 111, 104)
5. the depth of recursion is too high, which may cause the stack overflow, use BFS in that case.