Understanding the Problem

This problem asks for the the depth(integer) of the tree as a return. But there are things that I had to consider.

1. We do not know the depth of the tree, obviously

2. the parameter comes in TreeNode class type.

The class definition is as below.

# 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:

When the input root is [3,9,20,null,null,15,7], the expected output will be 3. But when I print the parameter root with print(root), the stdout is shown as,

# input
root = [3,9,20,null,null,15,7]

#output
3

# stdout
TreeNode{val: 3, left: TreeNode{val: 9, left: None, right: None}, right: TreeNode{val: 20, left: TreeNode{val: 15, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}}

If we visualise the intput root, it will be,

# visualised root
            3
        /       \
      9           20
   /     \       /   \
  null  null   15     7

Approach

At first I considered DFS to be implemented in the solution, setting up a stack and counting number. Then I again realised it had the root parameter in TreeNode type. It it was just a list I would’ve definitely gone for DFS, but in this case I was stunned as I did not know what to do with this problem.

I had no choice other than searching for hints for this question on LeetCode comments. Some did it with DFS and some complained about how incorrect and vague the instruction was.

I asked ChatGPT for clues and explanation to get closer the the solution of the problem. ChatGPT did a good work with explanation, but maybe not my brain this time. I was asking further information. It gave the answer that this problem was all about recursion.

I have never learned recursion before, although I know the concept of it, and recursive method seemed too far, far away from me as if it was not to be my algorithm skills thinking that this was a bit risky to use because it might cause memory burst, stack overflow.

Solution

So I learned about the recursive way to solve the problem from ChatGPT. It was as that simple. The tree is the nature of recursion and once I get to know the logic, it is understandable.

1. If root does not exist, return 0. This is very important to stop the recursion

2. Calculate left and right by calling self

3. return 1 + max(left, right) to get the sum of depth of the branches

# 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

        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        return 1 + max(left, right)

The left and right will always take root in the TreeNode form until the root is at None. for example,

Left branch

• at first depth 3 will have 9 as left and 20 as right.

• at the second depth on the left side, the root value will be 9, calling left and right again

• but at depth 3, left and right will both return 0 because of null values.

• back to the depth 2, it will have left and right as 0, so it will return 1 + 0.

Right branch

• at depth 2, root will be 20 and it will call left and right

• at depth 3, 15 which was the left from the depth 2, will have root as 15 and will call left and right

• at depth 4, root is null on both left and right so they will all return 0

• at depth 3, for root 15, it will have left and right with 0 values and it will only return 1+0

• for root 7 will return 1 the same as root 15

• at depth 2, left and right will have the value 1 each, which will return 1+1

At the first node

• left has returned 1 and right has returned 2 so far

• then 1 + max(left, right) will be 1 + max(1, 2), which will return 3 for the answer

Reflection

Recursive problem was always a threat to me, even by looking at it it sort of gave me a choking feeling. But as a person in IT industry and have come so far with master’s degree in AI, it is something that I need to cope with and discard fear to learn new things.

The process of recursion is complicated. For this reason I think I need to right down the process and try to track each return until I get it right.