Max Depth of A Tree - Depth First Search / DFS on Tree

Problems
1

https://algo.monster/problems/tree_max_depth

2

Dont mind me, just putting up the state version
def tree_max_depth(root: Node) → int:
def dfs(node, depth) → int:
if not node:
return depth
return max(dfs(node.left, depth+1), dfs(node.right, depth+1))
return dfs(root, 0)

3

The example code for doing a similar operation with global variables is WRONG and causes python to think I want to call an as of yet uninitialized local variable.

4

It’s pseudo code. In python, you can use nonlocal [or global if necessary] to access variables in the outer scope

https://www.learnbyexample.org/python-nonlocal-keyword/

5

Getting the following unhelpful error messages for multiple different inputs.

Compilation failed
Standard Output: No Output
Standard Error: No Output

6

I think it’s important to point out the actual problem being solved, not just the framework. Adding the +1 at the end of the return is where the actual operation happens: at each node, we’re aggregating the result of the child nodes using max, and then adding 1

1 Like
7

This solution is more readable:

def tree_max_depth(root: Node) → int:
# Base case, if we reach the end of any path
# return 0
if not root:
return 0

# Otherwise, for every call, return 1 for every node
# for both sides
left_depth = 1 + tree_max_depth(root.left)
right_depth = 1 + tree_max_depth(root.right)

# In the end, we want the largest number
return max(left_depth, right_depth)
8

From “Introduction to Tree Data Structure”:

Depth: the depth of a node is the number of edges on the path from the root to that node.

Doesn’t this mean the example at the top of the page has a max depth of 2? Instead of 3

9

The code is counting nodes that follow a certain path. There will always be for n nodes n-1 edges which is what depth counts for. So subtracting one from the final result gets the correct depth.

1 Like
10

it’s kinda disappointing that the website has so many bugs in it’s articles, the provided solution actullay calculates the MaxHeightOfaTree not MaxDepthOfaTree.

11

Sorry I was wrong, it doesn’t calculate neither of them.

12

Here is the solution:
public static int treeMaxDepth(Node root) {
// WRITE YOUR BRILLIANT CODE HERE
if(root == null)
return 0;
if(root.left == null && root.right == null)
return 0;
int l = treeMaxDepth(root.left);
int r = treeMaxDepth(root.right);
return Math.max(l,r) + 1;
}

1 Like
13

the question has been updated to use the consistent definition in the tree intro section.

17

I think there is a confusion about the definition of a tree’s depth.
Some resources states that root should be counted, so we are counting the number of nodes on the longest root to leaf path).
Other resources states the we should count the edges on the longest root to leaf path to get the depth of the tree.

Honestly I don’t know which definition is correct.
According to wikipedia and a high-rated stackoverflow article, AlgoMonster’s definition looks to be correct:
https://en.wikipedia.org/wiki/Tree_(data_structure)
https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

On the other side, the LeetCode’s similar problem, the root is also counted, and gives a different output.

19

I’m kind of puzzled why we introduced the idea of passing states as arguments and then didn’t use that idea in this question. It seemed like a good candidate for passing current depth as an argument. The following does this and passes all the test cases:
def tree_max_depth(root: Node, current_depth = 0) → int:
if not root:
if current_depth == 0:
return current_depth
return current_depth - 1
max_depth_left = tree_max_depth(root.left, current_depth + 1)
max_depth_right = tree_max_depth(root.right, current_depth + 1)

return max(max_depth_left, max_depth_right)
21

Hi, yes that works too! As explain in the previous article https://algo.monster/problems/dfs_on_trees_intro either way works.

23

This one is shorter. Any flaw with this?

   public static final int treeMaxDepth(Node root) {
      if (root == null) {
         return 0;
      } else {
         return Math.max(treeMaxDepth(root.getLeft()) + 1, treeMaxDepth(root.getRight()) + 1)
      }
   }
1 Like
24

My simple java solution

static int maxDepth=0;
public static int treeMaxDepth(Node<Integer> root) {
    // WRITE YOUR BRILLIANT CODE HERE
    maxDepth=0;
    calcMaxDepth(root,0);
    return maxDepth;
}

private static void calcMaxDepth(Node<Integer> root, int depth) {
    if(root==null)
    {
        if(depth-1>maxDepth)
        {
            maxDepth=depth-1;
        }
        return;
    }
    calcMaxDepth(root.left,depth+1);
    calcMaxDepth(root.right,depth+1);
}
25

For max-depth of binary tree, I feel like this way is easier to understand:

def tree_max_depth(root: Node) → int:
if root == None:
return 0

return 1 + max(tree_max_depth(root.left), tree_max_depth(root.right)) if root.left or root.right else 0
1 Like
26

Iterative DFS solution

function treeMaxDepth(root) {
    // WRITE YOUR BRILLIANT CODE HERE
    if(!root) return 0;
    
    let stack = [[root, 0]],
        ans = 0;
    
    while(stack.length > 0) {
        const item = stack.pop(),
              node = item[0],
              level = item[1];
        
        if(node.right) stack.push([node.right, level + 1]);
        if(node.left) stack.push([node.left, level + 1]);

        ans = Math.max(ans, level);
    }
    
    return ans;
      
}