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

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)

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.

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

Getting the following unhelpful error messages for multiple different inputs.

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

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

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)

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

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

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

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

Here is the solution:
public static int treeMaxDepth(Node root) {
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;

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

Inaccurate solution or description
Test 1:
5 4 3 x x 8 x x 6 x x
* /
* 4 6
* /
* 3 8

Prompt says, the output is 3, in the tests it expects a 2.

Nah, you’re just bad. Get Good

Space Complexity is O(n)

This website lacking hard!!! This “ex google” guy really charging this much and can’t even include space complexity?
What a con! I can make my own site and charge a fraction of what he is!!! Robbery!

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:

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

Dear AlgoMonster, please add the space complexity to your solutions. Thank you.

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)

hi, we added space complexity to every question

1 Like