Tree traversal - level order

tree_traversal_levelorder.py

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

def levelorder_traversal_recursive(root):
    result = []

    def recur(node, level):
        # base case:
        if not node:
            return

        # start a new level array
        if len(result) == level:
            result.append([])

        # append the current node value
        result[level].append(node.val)

        # process child nodes for the next level from left to right
        recur(node.left, level + 1)
        recur(node.right, level + 1)

    recur(root, 0)
    return result