# Sprint 3 Module Project 3

## isBalanced

"""
Understand

    1
  /    \
 2      3
       /
     4
True

    1
  /    \
 2      3
       /
     4
    /
   5
False

      1
     /
    2
   /
  3
False

Plan
Realize a few things:
1. A single node is balanced
2. To determine if a tree is balanced:
   2.1 both its left and right subtrees must be balanced
   2.2 the height difference between both left and right subtrees must differ no more than one

So, we just need to traverse the tree in a post-order manner. To determine if the entire tree is balanced, we must
determine that its subtrees are balanced. We recursively go through tree via recursion and a helper method. The helper
method will either tell us if a subtree is not balanced and its height. We'll use the result of this helper method to determine
if the entire tree and its subtrees are balanced.

Runtime: O(number of nodes) we'll visit each node once
Space: O(height of tree) imagine a degenerate/pathological/linked-list-like tree. Our call stack will grow at most its height
"""
def balancedBinaryTree(root):
    return isBalancedHelper(root) != -1

# Returns -1 if node is unbalanced, else return the max height starting at the node
def isBalancedHelper(node) -> int:
    if node == None:
        return 0

    if node.left == None and node.right == None:
        return 1

    leftHeight = isBalancedHelper(node.left)
    rightHeight = isBalancedHelper(node.right)

    if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:
        return -1

    return max(leftHeight, rightHeight) + 1

## Min Depth

from collections import deque

"""
Understand
    1
      \
       3
       /
     4
Output: 3

    1
  /    \
 2      3
       /
     4
Output: 2

    1
  /    \
 2      3
  \     /
   4   5
Output: 3

Plan
We can easily do a level-order traversal using a queue while keeping track of the level of the node enqueued.
The great thing about this approach is that since we're going through this level-by-level, the first leaf node we encounter is the most shallow leaf node.

We could also do a depth-first-traveral but that would be worse in the average case, consider this case:

    1
  /    \
 2      3
       /
     4
    /
   5

We'd still have to traverse all the nodes even though the most shallow leaf is very close to the root of the tree.

Runtime: O(number of nodes)
Space: O(max number of nodes in a level)
"""
def minimumDepthBinaryTree(root):
    if root == None:
        return 0
    queue = deque()
    queue.append((root, 1))
    while len(queue) > 0:
        curr = queue.popleft()
        currNode, currLevel = curr[0], curr[1]
        if currNode.left == None and currNode.right == None:
            return currLevel
        if currNode.left != None:
            queue.append((currNode.left, currLevel + 1))
        if currNode.right != None:
            queue.append((currNode.right, currLevel + 1))
    return -1