How do you find the maximum depth of a binary tree?
You look at the tree one level at a time and you keep a count of how deep you have gone. The depth of the tree is the number of levels from the root down to the deepest leaf.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def max_depth(root):
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
So how does it work? The depth of a tree with nothing in it is zero. The depth of any other tree is one, for the root, plus the bigger of the depths of the two sub-trees. So the recursive version asks the same question of the left side and the right side and takes the bigger answer.
the tree the depths of the sides the answer
---------------- ------------------------ --------
nothing 0 and 0 0
one node 0 and 0 1
root with a left 1 and 0 2
child
And the other way to do it is with a queue. You put the root in the queue, and then you take the nodes out one level at a time, counting the levels. That is the next question in this topic.
And the complexity is O of n for the time, because every node is visited once, and O of h for the space, where h is the height of the tree, because of the call stack in the recursive version. So a tree that is very deep uses a lot of stack.
And there is a detail worth knowing about. The depth of a tree with one node is one and not zero, because the root is on the first level. And an empty tree has a depth of zero, because there are no levels at all.
So the rule to remember is this. The depth is one plus the bigger of the two side depths, and an empty tree has a depth of zero.
The next two questions in this topic show the queue version and the version for a very deep tree.