Leetcode pattern: Tree DFS & BFS

How to study

1) Read this AWESOME article by Tim Park on BFS. Follow along the article to solve Leetcode #104

104. Maximum Depth of Binary Tree

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        queue = [(root, 1)]
        res = 0

        if root is None:
            return 0

        while queue:
            node, depth = queue.pop()
            res = max(res, depth)

            if node.left:
                queue.append((node.left, depth+1))
            if node.right:
                queue.append((node.right, depth+1))
        return res

BFS Pseudocode

def BFS(root):
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

2) Learn DFS by solving Leetcode #226

226. Invert Binary Tree

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        # swap
        temp = root.left
        root.left = root.right
        root.right = temp

        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

3) Read these AWESOME articles to understand why use stack for DFS and queue for BFS. (Focus on his handwritten notes image)

Leetcode Pattern 1 | BFS + DFS == 25% of the problems — part 1
Leetcode Pattern 1 | DFS + BFS == 25% of the problems — part 2

4) Refine intuition on "keeping track of results in a list" when using recursion in trees DFS

543. Diameter of Binary Tree

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = [0]
        def longestPath(node):
            if node is None:
                return 0
            
            left = longestPath(node.left)
            right = longestPath(node.right)

            res[0] = max(res[0], left + right)
            return max(left, right) + 1
        
        longestPath(root)
        return res[0]

110. Balanced Binary Tree

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True

        def findMaxDepth(node):
            if node is None:
                return [True, 0]
            
            left = findMaxDepth(node.left)
            right = findMaxDepth(node.right)

            balanced = (left[0] and right[0]) and abs(left[1]-right[1]) <= 1
                
            return [balanced, max(left[1], right[1])+1]
        
        return findMaxDepth(root)[0]

Common Edge Cases

#1 Tree empty

if root is None:
  return True

Notes

Important highlights from Tim Park's article (From Step 1 in How to study)

Storing additional data during traversal: store depth, current path, build a string or hold another node

We might want to store data when the answer deals with the node’s depth or requires us to pass information about nodes between nodes (aka build a string or path).

Think about the return value — What data do I need to solve this problem? A depth? A string?

Ask yourself what would be useful — What data could I have about the current node that would make this problem trivial?

Ask yourself can we pass this data along — What data could I pass from my current node to my children node’s to make this problem trivial?

Awesome Resources

Tree Question Pattern
https://leetcode.com/discuss/study-guide/1337373/Tree-question-pattern-oror2021-placement