Tree Traversal

Trees can be traversed in multiple ways. This document talks about multiple ways to traverse tree. I added templates for the such traversal here for easy reference and also set of sample problems to practice the templates on.

Level-wise Tree Traversal

A level-wise traversal of the tree can be described as visiting the nodes in the tree from root to the leaves such that all the parents at the same distance from root are visited before their children. A BFS can be used for such a traversal, the code for such BFS traversal looks very similar to the one in the graph traversal.

Below will define the define the template for such traversal and some problems based on the traversal.

Level Order Traversal Problem

def levelOrder(root: TreeNode):
  if root == None:
      return []
  sol = []
  # Create a double ended queue
  q = deque([root])
  # iterate till the q is empty
  while len(q) > 0:
      # Create level temp store list
      l = []
      # Iterate over the count of nodes in the q, all these nodes will be at the same level
      for _ in range(len(q)):
          # Pop from the left of the queue
          node = q.popleft()
          # Add the children to the queue.
          if node.left != None:
              q.append(node.left)
          if node.right != None:
              q.append(node.right)
          # Add the node to the level temp store
          l.append(node.val)
      # Add the temp store list to the solution
      sol.append(l)
  return sol

A TreeNode in a binary tree is described as: (This will be used as an input object for all subsequent templates too.)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Other similar problems can be based on above template with minor changes:

Level Order Traversal from bottom up

Same template, rather than using stack to store solution, use Deque and append to left of the queue.

N-array tree level order Traversal

Same template, with changes to iterate over the children rather than just adding left and right children.

Zig-Zag level order Traversal

Same Template, with changes to reverse the temp solution before adding it solution alternatively in level iteration.

Average of nodes at same level

Same Template, rather than accumulating the nodes value accumulate the sum and add average to solution.