Binary Tree Level Order Traversal

def traverse(root):

  if root is None:
    return []

  result = []
  queue = deque()

  queue.append(root)

  while len(queue) > 0:
    levelSize = len(queue)
    level = []

    for _ in range(levelSize):
      node = queue.popleft()
      level.append(node.val)

      if node.left:
        queue.append(node.left)

      if node.right:
        queue.append(node.right)
    
    result.append(level)

  return result

Reverse Level Order Traversal

Same as above. Only differences is that result will be a deque(), and for each level, we will appendleft to the result.

def traverse(root):
  result = deque()
  
  queue = deque()

  if root is None:
    return

  queue.append(root)

  while queue:
    currentSize = len(queue)
    currentLevel = []
    for _ in range(currentSize):
      temp = queue.popleft()
      currentLevel.append(temp.val)
      if temp.left is not None:
        queue.append(temp.left)
      if temp.right is not None:
        queue.append(temp.right)
        
    result.appendleft(currentLevel)

  return result

Zigzag Traversal

Similar to above. We will have a leftToRight boolen to keep track of whether we are prining in order or not for the current level. Also, we will use a deque() for the level, so that we can appendleft when leftToRight is False. Then we append to the result list by: result.append(list(currentLevel))

def traverse(root):
  result = []
  queue = deque()

  if root is None:
    return None

  queue.append(root)
  leftToRight = True

  while queue:
    currentSize = len(queue)
    currentLevel = deque()
    for _ in range(currentSize):
      temp = queue.popleft()

      if temp.left:
        queue.append(temp.left)

      if temp.right:
        queue.append(temp.right)

      if leftToRight:
        currentLevel.append(temp.val)
      else:
        currentLevel.appendleft(temp.val)
      
    result.append(list(currentLevel))
    leftToRight = not leftToRight

Level Averages in a Binary Tree

Same as above except calculating averages

def find_level_averages(root):
  result = []
  queue = deque()
  if root is None:
    return
  queue.append(root)
  while queue:
    levelSize = len(queue)
    levelSum = 0.0
    for _ in range(levelSize):
      temp = queue.popleft()
      levelSum += temp.val

      if temp.left is not None:
        queue.append(temp.left)

      if temp.right is not None:
        queue.append(temp.right)

    result.append(levelSum / float(levelSize))
  return result

Minimum Depth of a Binary Tree

Minimum depth is a level where a node has no children (is a leaf node).

def find_minimum_depth(root):

  if root is None:
    return 0

  currentDepth = 1
  queue = deque()
  queue.append(root)

  while queue:
    currentSize = len(queue)
    for _ in range(currentSize):
      node = queue.popleft()

      if not node.left and not node.right:
        return currentDepth
      
      if node.left:
        queue.append(node.left)

      if node.right:
        queue.append(node.right)

    currentDepth += 1

  return currentDepth

Level Order Successor

If the current node matches the key, then simply pop the next node to get the successor.

def find_successor(root, key):
  if root is None:
    return None
  
  queue = deque()
  queue.append(root)

  while queue:
    currentSize = len(queue)
    for _ in range(currentSize):
      temp = queue.popleft()

      if temp.left:
        queue.append(temp.left)
      if temp.right:
        queue.append(temp.right)
      
      if temp.val is key:
        successor = queue.popleft()
        return successor


  return None

Connect Level Order Siblings

Very similar to above. Just keep track of previous node. Connect previous node to current node. At the start of each level, previous node is set to None, so the last node on each level has a .next that remains None.

def connect_level_order_siblings(root):
  if root is None:
    return None
  
  queue = deque()
  queue.append(root)
  while queue:
    currentSize = len(queue)
    previousNode = None
    for _ in range(currentSize):
      currentNode = queue.popleft()
      if previousNode:
        previousNode.next = currentNode
      previousNode = currentNode

      if currentNode.left:
        queue.append(currentNode.left)
      if currentNode.right:
        queue.append(currentNode.right)
      
  return

Connect All Level Order Siblings

Pretty much the same as above, except keep track of previous node between levels. Also, don't need to process levels differently, so no need to use for _ in currentSize loop.

def connect_all_siblings(root):
  if root is None:
    return

  queue = deque()
  queue.append(root)
  previousNode = None

  while queue:
    
    node = queue.popleft()
    if previousNode:
      previousNode.next = node
    
    if node.left:
      queue.append(node.left)

    if node.right:
      queue.append(node.right)

    previousNode = node

  return root

Right View of a Binary Tree

Easy. When you are at the last node for a given level, append it to result.

def tree_right_view(root):
  result = []
  queue = deque()
  queue.append(root)

  while queue:
    levelSize = len(queue)
    for i in range(levelSize):
      node = queue.popleft()

      if node.left:
        queue.append(node.left)

      if node.right:
        queue.append(node.right)

      # If this is the last (rightmost) node of the level
      if i == (levelSize - 1):
        result.append(node)
        
  return result