Learn
Recursion vs. Iteration - Coding Throwdown

Binary trees, trees which have at most two children per node, are a useful data structure for organizing hierarchical data.

It’s helpful to know the depth of a tree, or how many levels make up the tree.

``````# first level
root_of_tree = {"data": 42}
# adding a child - second level
root_of_tree["left_child"] = {"data": 34}
root_of_tree["right_child"] = {"data": 56}
# adding a child to a child - third level
first_child = root_of_tree["left_child"]
first_child["left_child"] = {"data": 27}``````

Here’s an iterative algorithm for counting the depth of a given tree.

We’re using Python dictionaries to represent each tree node, with the key of `"left_child"` or `"right_child"` referencing another tree node, or `None` if no child exists.

``````def depth(tree):
result = 0
# our "queue" will store nodes at each level
queue = [tree]
# loop as long as there are nodes to explore
while queue:
# count the number of child nodes
level_count = len(queue)
for child_count in range(0, level_count):
# loop through each child
child = queue.pop(0)
# add its children if they exist
if child["left_child"]:
queue.append(child["left_child"])
if child["right_child"]:
queue.append(child["right_child"])
# count the level
result += 1
return result

two_level_tree = {
"data": 6,
"left_child":
{"data": 2}
}

four_level_tree = {
"data": 54,
"right_child":
{"data": 93,
"left_child":
{"data": 63,
"left_child":
{"data": 59}
}
}
}

depth(two_level_tree)
# 2
depth(four_level_tree)
# 4``````

This algorithm will visit each node in the tree once, which makes it a linear runtime, `O(N)`, where `N` is the number of nodes in the tree.

### Instructions

1.

Implement your version of `depth()` which has the same functionality using recursive calls!