104. Maximum Depth of Binary Tree

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

Problem Description

In this LeetCode problem, we are given a binary tree, which is a tree data structure where each node has at most two children, referred to as the left child and the right child. The task is to find the maximum depth of the tree. The maximum depth is defined as the length of the longest path from the root node of the tree down to the farthest leaf node. The length of a path is measured by the number of nodes along that path. In this context, a leaf node is a node with no children, signifying that it's at the edge of the tree.

Intuition

To determine the solution to finding the maximum depth of a binary tree, we can use a strategy known as depth-first search (DFS).

The intuition behind the approach is quite straightforward:

  • If we start at the root and the tree is empty, the maximum depth is zero.
  • If the tree is not empty, we can recursively find the maximum depth of the left and right subtrees.
  • The maximum depth of the tree would then be the larger of the two maximum depths found, plus one for the root node itself.

This recursive strategy hinges upon the idea that the depth of a tree is equal to the depth of its deepest subtree, plus a factor of one for the root. As we explore each subtree, we keep on asking the same question, 'what's the maximum depth from this node down?'. We keep on doing this recursively until we reach the leaf nodes, which have a depth of zero since there are no further nodes below them.

The solution leverages this idea and recursively descends through the tree, ensuring that the maximum depth is calculated for each subtree. Once the recursion reaches the leaf nodes, it begins to unwind, cumulatively calculating the depth by comparing the depths of the left and right subtrees at each step, and adding one to account for the current node's depth contribution. By the time the recursion unwinds back to the root, we would have found the maximum depth.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What data structure does Breadth-first search typically uses to store intermediate states?

Solution Approach

The solution provided is an example of a depth-first search (DFS) algorithm implemented using recursion, which is a common pattern for traversing trees. The approach is simple and consists of the following steps:

  1. Base Case Check: At the start of the maxDepth method, the base case checks if the current node, initially the root, is None. If it is, this means that we have hit the bottom of the tree (or the tree is empty to begin with), and we return 0 as the depth. Every leaf will eventually hit this base case.

    1if root is None:
2    return 0

  2. Recursive Calls: If the node is not None, we proceed to make recursive calls for the left child and right child of the current root node.

    1l, r = self.maxDepth(root.left), self.maxDepth(root.right)

    By calling self.maxDepth on root.left and root.right, we are asking for the maximum depth from each child node.

  3. Calculating Depth: After receiving the maximum depths from the left and right subtrees (l and r), we calculate the maximum depth of the current tree by taking the max of l and r, and adding 1 to account for the current root node.

    1return 1 + max(l, r)

  4. Climbing up the Recursion: This step essentially repeats for each node in the tree until all nodes have been visited, and at each step, we climb up the tree's layers, cumulatively calculating the maximum depth by comparing the depths from the left and right.

The choice of DFS and recursion in this case allows for an elegant and easily understandable solution to the problem. It's worth mentioning that every time a recursive call is made, the call stack keeps track of each node's state, enabling the process to 'remember' the paths taken once it needs to return and subsequently combine the depths found.

Overall, this implementation relies heavily on the nature of recursion to break down the problem into manageable pieces, solve each minor problem, and combine the results to arrive at the final solution, serving as a clear illustration of a divide-and-conquer strategy.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's illustrate the solution approach using a small example of a binary tree. Assume we have the following binary tree:

1       1
2      / \
3     2   3
4    / \   \
5   4   5   6
6  /         \
7 7           8

In this tree, the root node is 1, and its left child is 2, and its right child is 3. Continuing down the tree, 2 has two children 4 and 5, and 3 has one child 6. On the next level, 4 has one child 7 and 6 has one child 8. The leaf nodes in this tree are 5, 7, and 8.

Let's walk through the recursive solution to find the maximum depth of this tree:

  1. Starting at the root node (1):

    • The maxDepth method is called with the root node 1. Since 1 is not None, we perform the recursive calls on its children (2 and 3).

  2. Explore the left subtree of node (2):

    • The maxDepth method is called on the left child (2), which is not None. Recursive calls are made on its children (4 and 5).

  3. Explore the left subtree of node (4):

    • Continuing the recursion, maxDepth is called on the child 4. It has a left child 7, so another recursive call is made.

  4. Leaf node (7):

    • The maxDepth method is called on 7. With no children, 7 is a leaf node, reaching the base case. Hence, it returns 0, indicating a node's depth is zero below it.

  5. Climb up from leaf node (7) to node (4):

    • Since 4 has no right child, it compares the depths of left (0+1) and (non-existent) right subtrees and returns 1.

  6. Climb up to node (2):

    • Now we consider node 5, which is a leaf node. It hits the base case and returns 0.
    • Back at node 2, we compare the maximum depths received from 4 (1) and 5 (0), and add 1 for the node 2 itself. So 2 returns 2.

  7. Explore the right subtree of node (3):

    • The recursion calls maxDepth on node 3. It has a right child 6, so we call maxDepth on 6.

  8. Explore the right subtree of node (6):

    • Node 6 has a right child 8, and invoking maxDepth on 8 leads to a base case returning 0.

  9. Climb up from leaf node (8) to node (6):

    • Node 6 has no left child, so it takes the maximum of left (non-existent) and right (0+1) depths, resulting in 1.

  10. Climb up to node (3):

    • At node 3, we compare the maximum depths from 6 (1), and since 3 has no left child, we conclude node 3's subtree has a maximum depth of 2 (1 from 6 plus 1 for the 3 itself).

  11. Combine results at the root node (1):

    • Finally, at the root node 1, we compare the depths received from 2 (2) and 3 (2), taking the maximum, which is 2, and add 1 for the root node. Hence, we determine that the maximum depth of the tree is 3.

This recursive process explored each subtree, remembered the maximum depth at each level, and combined the results to deliver the overall maximum depth.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def maxDepth(self, root: TreeNode) -> int:
10        # If the current node is None, it means this is an empty tree or we've reached the end of a branch.
11        # Return 0 in this case as it contributes no depth.
12        if root is None:
13            return 0
14
15        # Recursively find the depth of the left subtree.
16        # This will traverse all the way down to the leftmost leaf node.
17        left_depth = self.maxDepth(root.left)
18
19        # Recursively find the depth of the right subtree.
20        # This will traverse all the way down to the rightmost leaf node.
21        right_depth = self.maxDepth(root.right)
22
23        # The maximum depth of the current node will be 1 (for the current node) plus the maximum
24        # of the depths of its left and right subtrees.
25        # This ensures that the longest path from root to leaf is counted.
26        return 1 + max(left_depth, right_depth)
27
1// Definition for a binary tree node.
2class TreeNode {
3    int value;
4    TreeNode left;
5    TreeNode right;
6
7    // Constructor to create a leaf node.
8    TreeNode(int value) {
9        this.value = value;
10    }
11
12    // Constructor to create a node with specific children.
13    TreeNode(int value, TreeNode left, TreeNode right) {
14        this.value = value;
15        this.left = left;
16        this.right = right;
17    }
18}
19
20class Solution {
21    // Calculates the maximum depth of a binary tree.
22    public int maxDepth(TreeNode root) {
23        // If the root is null, the depth is 0.
24        if (root == null) {
25            return 0;
26        }
27
28        // Recursively compute the depth of the left subtree.
29        int leftDepth = maxDepth(root.left);
30
31        // Recursively compute the depth of the right subtree.
32        int rightDepth = maxDepth(root.right);
33
34        // The depth of the current node is the greater of its two children's depths plus one.
35        return 1 + Math.max(leftDepth, rightDepth);
36    }
37}
38
1// Definition for a binary tree node.
2struct TreeNode {
3    int val; // value of the node
4    TreeNode *left; // pointer to the left child
5    TreeNode *right; // pointer to the right child
6
7    // Constructor to initialize the node with a value, and nullptr for children
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9
10    // Constructor to initialize the node with a value and no children
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12
13    // Constructor to initialize the node with a value and left and right children
14    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
15};
16
17class Solution {
18public:
19    // Function to find the maximum depth of a binary tree.
20    int maxDepth(TreeNode* root) {
21        // Base case: if the current node is null, return 0 as the depth
22        if (!root) 
23            return 0;
24
25        // Recursively compute the depth of the left subtree
26        int leftDepth = maxDepth(root->left);
27        // Recursively compute the depth of the right subtree
28        int rightDepth = maxDepth(root->right);
29
30        // The maximum depth of the current node is 1 (for the current node) plus
31        // the greater depth between the left and right subtrees
32        return 1 + std::max(leftDepth, rightDepth);
33    }
34};
35
1/**
2 * Definition for a binary tree node.
3 */
4interface TreeNode {
5  val: number;
6  left: TreeNode | null;
7  right: TreeNode | null;
8}
9
10/**
11 * This function computes the maximum depth of a binary tree.
12 * The maximum depth is the number of nodes along the longest path
13 * from the root node down to the farthest leaf node.
14 *
15 * @param {TreeNode | null} root - The root node of the binary tree.
16 * @return {number} The depth of the binary tree.
17 */
18function maxDepth(root: TreeNode | null): number {
19    // An empty tree has a depth of zero
20    if (root === null) {
21        return 0;
22    }
23    // Recursively compute the depth of the left and right subtree
24    // and return the greater one increased by 1 for the current node
25    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
26}
27
Not Sure What to Study? Take the 2-min Quiz๏ผš

How does quick sort divide the problem into subproblems?

Time and Space Complexity

Time Complexity: The time complexity of the code is O(n), where n is the number of nodes in the tree. This is because the algorithm is a depth-first search, and it visits each node exactly once to determine the maximum depth.

Space Complexity: The space complexity of the code is O(h), where h is the height of the tree. This space is used by the call stack during the recursion. In the worst case, if the tree is completely unbalanced, with all nodes on one side, the height of the tree h can be equal to n, leading to a space complexity of O(n). In the best case, for a completely balanced tree, the height h would be log(n), leading to a space complexity of O(log(n)).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ