binary tree level order traversal

Go Back home

Recursive

 1 from collections import defaultdict
 2 
 3 def binary_tree_depth_order(tree):
 4     def helper(node, depth):
 5         result[depth].append(node.data)
 6         if node.left:
 7             helper(node.left, depth+1)
 8         if node.right:
 9             helper(node.right, depth+1)
10     result = defaultdict(list)
11     helper(tree, 0)
12     return [*result.values()]

Iterative

 1 def binary_tree_depth_order(tree):
 2 
 3     result = []
 4     if not tree:
 5         return result
 6 
 7     curr_depth_nodes = [tree]
 8     while curr_depth_nodes:
 9         result.append([curr.data for curr in curr_depth_nodes])
10         curr_depth_nodes = [
11             child for curr in curr_depth_nodes
12             for child in (curr.left, curr.right) if child
13         ]
14     return result