[Leetcode] Maximum Depth of Binary Tree

Given the rootof a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

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

-100 <= Node.val <= 100

How to understand?

There is binary tree which has a root node, left node, and right node. it will continue to the end of the entire tree. The solution of this problem should find the deepest node and return the depth of the entire tree. How to do that? Explain the level of each node approaching level by level OR find the deepest node and return the depth of the node → "find the longest path from the root to a leaf, and return its length.".

How TO appRoach?

Recursion

function maxDepth(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    const left_height = maxDepth(root.left);
    const right_height = maxDepth(root.right);
    return 1 + Math.max(left_height, right_height);
}

Use recursion using itself. Each node has value, left, and right. Return the +1 depth each time to get the height at the node recursively. It will return the depth at the last deepest node.

BFS , Tail recursion

class Solution:
    def __init__(self):

        self.next_items = []
        self.max_depth = 0

    def next_maxDepth(self):
        if not self.next_items:
            return self.max_depth
        next_node, next_level = self.next_items.pop(0)
        next_level += 1
        self.max_depth = max(self.max_depth, next_level)
    
        if next_node.left:
            self.next_items.append((next_node.left, next_level))
        if next_node.right:
            self.next_items.append((next_node.right, next_level))

        return self.next_maxDepth()

    def maxDepth(self, root):
        if not root:
            return 0

        self.next_items = []
        self.max_depth = 0
        self.next_items.append((root, 0))
        return self.next_maxDepth()

Use tail recursion. maxDepth will has root node and initialise the next_items array and max_depth.

use those 2 values and return the next_maxDepth at the end of the solution. That will return the maxDepth recursively in it.

keep the level +1 since it approaches all the node in the same level. and compare it to the max_depth so far and append the left node and right node in the function.

DFS , Iteration

function maxDepth(root: TreeNode | null): number {
    if (root == null) {
        return 0;
    }
    let stack: [TreeNode | null, number][] = [];
    stack.push([root, 1]);
    let depth = 0;
    while (stack.length !== 0) {
        let [node, current_depth] = stack.pop() as [TreeNode, number];
        if (node != null) {
            depth = Math.max(depth, current_depth);
            stack.push([node.left, current_depth + 1]);
            stack.push([node.right, current_depth + 1]);
        }
    }
    return depth;
}

Use stack to catch up the nodes to be visited next time.

check the length of stack and pop the item to visit.

when the node is not null then compare the depth and push the left and right node.

use the pair of node itself and depth.

lastly return the depth.