104 — Maximum Depth of a Binary Tree

Restating Info We’re Already Given:

• We want to find the maximum depth of the binary tree, beginning at depth 1 for the root.

Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):

• Do you care if I do this iteratively or recursively?

Discuss Recursive Solution:

One way we can solve this is recursively. To do so, we will call the function again on the left and right nodes from root, adding 1 for each intermediary calculation from root to current node.

Code Recursive Solution:

Discuss Iterative Solution:

Tail recursion is not supported in Python. However, all recursive functions can be solved iteratively and vice versa. This can be proven by the fact that μ-recursive functions and non recursive calculus are both Turing complete. All Turing calculi are equivalent in expressive power and thus all iterative functions can be written recursively.

Here, we solve this iteratively by using a stack to store node, depth tuples. For each tuple, we compare its depth to the maximum depth seen so far before adding potentially existent left and right nodes with a depth incremented by 1.

Code Iterative Solution:

Runtime/Space Complexity:

Both iterative and recursive solutions run in linear time, visiting each node once.

However, the recursive solution has a worst case space complexity linear to the number of nodes. The binary tree would have all nodes on one side, so the recursive call would calculate each node’s value based on the former and traverse all the way down to the leaf node. In the iterative solution, the worst case space complexity would also be linear as we append nodes at the next depth that exist. In a simple case where we have a 3 node binary tree with a root node containing a left and right, the nodesToVisit stack begins with 1 node, which is removed before the 2 nodes (left and right) are added. With 2/3 nodes being in the nodesToVisit, this makes the space complexity O(n) at worst.

Note: In the scenario where the binary tree is completely imbalanced, (i.e. only goes to the left or only goes to the right) then the nodesToVisit is optimal as we only add nodes that exist. Thus, we only add 1 node for every node visited, keeping that call stack constant.

Test Cases:

• Empty binary tree
• Binary tree with 1 node
• Binary tree