Solution: Maximum Depth of Binary Tree

Statement#

You are given the root of a binary tree, and your task is to determine the maximum depth of this tree. The maximum depth of a binary tree is determined by the count of nodes found on the longest path from the root node to the farthest leaf node.

Constraints:

• The number of nodes in the tree is in the range $[0, 10^4].$

• $-100 \leq$Node.data $\leq 100$

Solution#

The approach which we will be using to solve this problem is iterative depth-first search. We visit all the nodes of the given binary tree, starting from the root node. A stack is used to keep track of the visited nodes along with the depth at which they are located. Once all the nodes of the tree have been traversed, we return the maximum depth max_depth we have calculated so far.

To obtain this solution, the following procedure can be adopted:

1. We initialize a stack nodes_stack to keep track of nodes for exploration. In the nodes_stack, we start with a tuple containing the root node and a depth of $1$.

2. Initialize a variable max_depth with $0$ to keep track of the maximum depth that is calculated so far.

3. Iterate over nodes_stack and pop its top element. If this node has a left child, create a tuple consisting of the left child node, and an incremented depth (depth + 1), and push this tuple onto the stack. Likewise, a similar tuple is added to the stack if the right child exists.

4. When a leaf node, i.e., a node with no left or right child, is encountered, check if depth is greater than max_depth. In that case, update max_depth to the value of depth.

5. After traversing all nodes, return max_depth, representing the maximum depth of the binary tree.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s implement the algorithm as discussed above.

Time complexity#

The time complexity of the given code is $O(n)$, where $n$ is the number of nodes in the binary tree.

Space complexity#

The space complexity of the given code is $O(\log n)$. Since at any given point during the traversal, the number of nodes in the stack is a function of the current distance from the root.