Jobs

Interviews

Discussions

Maximum Depth of Binary Tree

Easy

Uber

0 views

Topics:

TreesRecursion

Given the root of 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.

For example:

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

In this example, the tree looks like this:

Another example:

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

In this case, the tree is:

1 \ 2

Could you provide an algorithm to find the maximum depth of a binary tree? What is the time and space complexity of your approach? Are there any edge cases to consider? Please explain your reasoning.

Maximum Depth of Binary Tree

Easy

Uber

0 views

Topics:

TreesRecursion

Given the root of 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.

For example:

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

In this example, the tree looks like this:

Another example:

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

In this case, the tree is:

1 \ 2

Could you provide an algorithm to find the maximum depth of a binary tree? What is the time and space complexity of your approach? Are there any edge cases to consider? Please explain your reasoning.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary tree be empty (i.e., root is null)? If so, what should I return?
What data type are the node values, and are there any restrictions on their range (e.g., can they be negative or floating-point numbers)?
By 'depth', do you specifically mean the number of nodes from the root to the farthest leaf, or the number of edges?
Is the input always a valid binary tree, or do I need to handle cases where the tree structure is invalid (e.g., cycles)?
Are we concerned about stack overflow issues for extremely deep trees, or can I assume the depth will be within reasonable limits for a recursive solution?

Brute Force Solution

Approach

The goal is to find how deep a tree is by checking every path from the top to the bottom. We will explore each possible route to find the longest one. Think of it as trying every single road in a maze to see which one is the longest.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Go down the left path, and keep going until you can't go any further.
Count how many steps you took to get to the bottom of that left path.
Now, go back to the top and go down the right path, again going as far as you can.
Count how many steps you took to get to the bottom of that right path.
Compare the number of steps from the left path and the right path. The bigger number is the depth of the tree along that branch.
Remember that depth, and then do this same process for every single part of the tree, every branch, until you've explored absolutely every possible path from the top all the way to a bottom.
After checking every path, find the biggest depth you found. That's the maximum depth of the whole tree.

Code Implementation

def maximum_depth_of_binary_tree_brute_force(root):
    maximum_depth = 0

    def calculate_depth(node, current_depth):
        nonlocal maximum_depth

        # If we've hit a leaf, compare this path's depth.
        if node is None:

            maximum_depth = max(maximum_depth, current_depth)
            return

        # Traverse the left subtree.
        calculate_depth(node.left, current_depth + 1)

        # Traverse the right subtree.
        calculate_depth(node.right, current_depth + 1)

    # Initiate the recursive depth calculation.
    calculate_depth(root, 0)

    return maximum_depth

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once to determine the maximum depth. The 'try every single road in a maze' analogy refers to a depth-first traversal of the tree. Since each node is visited only once, the time complexity is directly proportional to the number of nodes, n. Therefore, the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity

O(N) – The algorithm explores each path from the root to every leaf node using recursion. In the worst-case scenario (a skewed tree), the recursion stack can grow to the height of the tree, which could be N, where N is the number of nodes. Therefore, the maximum space used by the call stack will be proportional to the number of nodes N. This leads to a space complexity of O(N).

Optimal Solution

Approach

The best way to find the maximum depth of a binary tree is to explore it level by level. We use a method where we go as deep as possible on each side and keep track of the deepest point we reach.

Here's how the algorithm would work step-by-step:

Think of starting at the very top of the tree, the root.
From the root, go down one level to the left, and then go down as far as you can on that side, counting how many levels you pass through.
Do the same thing going down to the right side from the root, again counting levels.
Compare the level counts from going left and going right. The bigger number is the depth of that section of the tree.
Repeat this process for every starting point in the tree, but only if it's deeper than anything seen before.
The biggest number you found after checking every spot is the overall maximum depth of the whole tree.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def max_depth_binary_tree(root):
    if root is None:
        return 0

    # Recursively calculate the depth of the left subtree
    left_subtree_depth = max_depth_binary_tree(root.left)

    # Recursively calculate the depth of the right subtree
    right_subtree_depth = max_depth_binary_tree(root.right)

    # Return the maximum depth of either subtree, plus 1 for the current node.
    return max(left_subtree_depth, right_subtree_depth) + 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm, as described, visits each node in the tree once to determine the maximum depth. It recursively explores both the left and right subtrees of each node. In the worst-case scenario, it traverses all n nodes of the tree. Therefore, the time complexity is directly proportional to the number of nodes.

Space Complexity

O(N) – The provided explanation describes a depth-first traversal of the tree using recursion. In the worst-case scenario, the tree is completely unbalanced (e.g., a linked list), and the algorithm may need to explore N levels deep, where N is the number of nodes in the tree. Each recursive call adds a new frame to the call stack. Therefore, the maximum space used by the recursion stack is proportional to the height of the tree, which can be N in the worst case. Hence, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty root node	If the root is null, the maximum depth is 0, return 0 to handle the empty tree case.
Single node tree (only root)	If the root has no children, the maximum depth is 1, as it has one node in the path.
Completely unbalanced tree (left or right skew)	The recursive or iterative DFS/BFS will traverse the entire skewed path, correctly determining the depth.
Large tree (high depth)	The recursive approach might hit stack overflow limits for extreme depths, making an iterative BFS approach preferable for very deep trees.
Tree with negative node values (though not depth-related, confirms general handling)	Node values do not affect depth calculation; algorithm works regardless of node value signs.
Maximum integer values for node values (tests potential numerical issues, not depth related)	Depth calculation does not use node values, so Integer.MAX_VALUE values will not influence depth result.
Perfectly balanced tree	The algorithm should correctly and efficiently calculate the depth of a perfectly balanced tree due to the uniform depth of all paths.
Binary tree with duplicate depths (different paths of same length)	The algorithm finds the maximum depth, so multiple paths of the same maximum length are irrelevant.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary tree be empty (i.e., root is null)? If so, what should I return?
What data type are the node values, and are there any restrictions on their range (e.g., can they be negative or floating-point numbers)?
By 'depth', do you specifically mean the number of nodes from the root to the farthest leaf, or the number of edges?
Is the input always a valid binary tree, or do I need to handle cases where the tree structure is invalid (e.g., cycles)?
Are we concerned about stack overflow issues for extremely deep trees, or can I assume the depth will be within reasonable limits for a recursive solution?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Go down the left path, and keep going until you can't go any further.
Count how many steps you took to get to the bottom of that left path.
Now, go back to the top and go down the right path, again going as far as you can.
Count how many steps you took to get to the bottom of that right path.
Compare the number of steps from the left path and the right path. The bigger number is the depth of the tree along that branch.
Remember that depth, and then do this same process for every single part of the tree, every branch, until you've explored absolutely every possible path from the top all the way to a bottom.
After checking every path, find the biggest depth you found. That's the maximum depth of the whole tree.

Code Implementation

def maximum_depth_of_binary_tree_brute_force(root):
    maximum_depth = 0

    def calculate_depth(node, current_depth):
        nonlocal maximum_depth

        # If we've hit a leaf, compare this path's depth.
        if node is None:

            maximum_depth = max(maximum_depth, current_depth)
            return

        # Traverse the left subtree.
        calculate_depth(node.left, current_depth + 1)

        # Traverse the right subtree.
        calculate_depth(node.right, current_depth + 1)

    # Initiate the recursive depth calculation.
    calculate_depth(root, 0)

    return maximum_depth

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The best way to find the maximum depth of a binary tree is to explore it level by level. We use a method where we go as deep as possible on each side and keep track of the deepest point we reach.

Here's how the algorithm would work step-by-step:

Think of starting at the very top of the tree, the root.
From the root, go down one level to the left, and then go down as far as you can on that side, counting how many levels you pass through.
Do the same thing going down to the right side from the root, again counting levels.
Compare the level counts from going left and going right. The bigger number is the depth of that section of the tree.
Repeat this process for every starting point in the tree, but only if it's deeper than anything seen before.
The biggest number you found after checking every spot is the overall maximum depth of the whole tree.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def max_depth_binary_tree(root):
    if root is None:
        return 0

    # Recursively calculate the depth of the left subtree
    left_subtree_depth = max_depth_binary_tree(root.left)

    # Recursively calculate the depth of the right subtree
    right_subtree_depth = max_depth_binary_tree(root.right)

    # Return the maximum depth of either subtree, plus 1 for the current node.
    return max(left_subtree_depth, right_subtree_depth) + 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty root node	If the root is null, the maximum depth is 0, return 0 to handle the empty tree case.
Single node tree (only root)	If the root has no children, the maximum depth is 1, as it has one node in the path.
Completely unbalanced tree (left or right skew)	The recursive or iterative DFS/BFS will traverse the entire skewed path, correctly determining the depth.
Large tree (high depth)	The recursive approach might hit stack overflow limits for extreme depths, making an iterative BFS approach preferable for very deep trees.
Tree with negative node values (though not depth-related, confirms general handling)	Node values do not affect depth calculation; algorithm works regardless of node value signs.
Maximum integer values for node values (tests potential numerical issues, not depth related)	Depth calculation does not use node values, so Integer.MAX_VALUE values will not influence depth result.
Perfectly balanced tree	The algorithm should correctly and efficiently calculate the depth of a perfectly balanced tree due to the uniform depth of all paths.
Binary tree with duplicate depths (different paths of same length)	The algorithm finds the maximum depth, so multiple paths of the same maximum length are irrelevant.