Tree Traversal and Patterns

To get to it straight - here's some scribbles and tricks around Tree Traversals that will assist you in your problem solving journey.

When tree elements are represented in the form of a list:

In In-Order traversal of a BT, items to the left of the root are in the left sub-tree and items to the right of the root are in the right sub-tree. So if 1 is root in [4 2 5 1 3], then 4,2,5 lie in the left sub-tree and 3 lies in the right sub-tree. This property can be used to reconstruct BT just from a given list of elements
Extending this to the post-order traversal, the last item is the root of the BT. So 3 becomes the root in the above list
For pre-order traversal of a BST the list of elements will be a sorted array and computation of the middle will give us the root

Level-order traversals:

are helpful when we need to do computation at different node levels like sum or average at each level
to do this we need to start with a list with just the root in it. As we go down, we keep on updating this list with the nodes to both left and right of the root

level = [root]
while root and level:
    current, next = [], []
    for node in level:
        current.append(node.val)
        if node.left:
            next_level.append(node.left)
        if node.right:
            next_level.append(node.right)
        # do something with the current like sum(current)
        level = next_level

Recursion in trees

when return type is TreeNode itself, recursion breaking condition would be if not root: return None. We do our processing, generate remaining parts of the tree (usually its root.left/right = recursive_function(arg)). Finally, we return the root when we are finished. Instead of checking if not root, we can also do if root: process
when return type is some int (may be max, min or some other value calculated during some processing on the tree), recursive function won't be used to form part of root(left or root). Instead, it would be used to compute some value (remember our return type was int?). In this case we break the recursion by 'if not root: return 0' (cause once again we need to return an int)

EXAMPLE: to calculate the min depth of a BT:

def minDepth(self, root):
            if not root:
                return 0
            ld = rd = 0
            if root.left: ld = self.maxDepth(root.left)
            if root.right: rd = self.maxDepth(root.right)
            return ld + rd + 1 if ld == 0 or rd == 0 else min(ld, rd) + 1

Dealing with paths:

Problems where we have to go down all paths and perform some computations. This is nothing but DFS + path memorization.

use stack and iterative approach
customize stack to store the stuff you need, for instance: stack[(node, computation, [path])]
keep updating node, computation and path as we go left and right

related problems : path sum (I, II and III), count good nodes

thelongfatnetwork's blog