LeetCode 104: Maximum Depth of Binary Tree

Recursive

$\text{MaxDepth}(root) = \begin{cases} 0, & \text{if } root = \texttt{None} \\ \max{ \left( \text{MaxDepth}(root.left), \text{MaxDepth}(root.right) \right) } + 1 & \text{otherwise} \end{cases}$

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(\texttt{tree-height})$ .

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

Iterative

Simulate the bottom up recursion with stack, visited set, and node height dict.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(\texttt{tree-height})$ .

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        visited = set()
        node_height = {}
        stack = [root]
        while stack:
            u = stack.pop()
            if not u.left and not u.right:
                node_height[u] = 1
                continue
            if u not in visited:
                visited.add(u)
                stack.extend(v for v in (u, u.left, u.right) if v)
                continue
            # Return path: heights of u's children are available
            node_height[u] = (
                max(node_height.get(u.left, 0), node_height.get(u.right, 0)) + 1
            )

        return node_height[root]

Use threaded binary tree or Morris traversal.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(1)$ .

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        depth, max_depth = 0, 0
        while root:
            if not root.left:
                root = root.right
                depth += 1
                max_depth = max(max_depth, depth)
                continue
            steps, pred = 1, root.left
            while pred.right and pred.right != root:
                pred = pred.right
                steps += 1
            if not pred.right:
                pred.right = root
                root = root.left
                depth += 1
                max_depth = max(max_depth, depth)
            else:
                pred.right = None
                depth -= steps
                root = root.right

        return max_depth

unreasonably effective