2

I am having trouble understanding this maxDepth code. Any help would be appreciated. Here is the snippet example I followed.

int maxDepth(Node *&temp)
{
  if(temp == NULL)
  return 0;

 else
{
 int lchild = maxDepth(temp->left);
 int rchild = maxDepth(temp->right);

 if(lchild <= rchild)
 return rchild+1;

 else
  return lchild+1;

 }

}

Basically, what I understand is that the function recursively calls itself (for each left and right cases) until it reaches the last node. once it does, it returns 0 then it does 0+1. then the previous node is 1+1. then the next one is 2+1. if there is a bst with 3 left childs, int lchild will return 3. and the extra + 1 is the root. So my question is, where do all these +1 come from. it returns 0 at the last node but why does it return 0+1 etc. when it goes up the left/right child nodes? I don't understand why. I know it does it, but why?

Improve this question
1
  • Euh, because if there's a new node, then the depth is the previous plus one, perhaps? Commented Oct 22, 2012 at 16:32

8 Answers 8

Reset to default
8

Consider this part (of a bigger tree):

       A
        \
         B

Now we want to calculate the depth of this treepart, so we pass pointer to A as its param.

Obviously pointer to A is not NULL, so the code has to:

  • call maxDepth for each of A's children (left and right branches). A->right is B, but A->left is obviously NULL (as A has no left branch)

  • compare these, choose the greatest value

  • return this chosen value + 1 (as A itself takes a level, doesn't it?)

Now we're going to look at how maxDepth(NULL) and maxDepth(B) are calculated.

The former is quite easy: the first check will make maxDepth return 0. If the other child were NULL too, both depths would be equal (0), and we have to return 0 + 1 for A itself.

But B is not empty; it has no branches, though, so (as we noticed) its depth is 1 (greatest of 0 for NULLs at both parts + 1 for B itself).

Now let's get back to A. maxDepth of its left branch (NULL) is 0, maxDepth of its right branch is 1. Maximum of these is 1, and we have to add 1 for A itself - so it's 2.

The point is the same steps are to be done when A is just a part of the bigger tree; the result of this calculation (2) will be used in the higher levels of maxDepth calls.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

5

Depth is being calculated using the previous node + 1

Improve this answer

Comments

4

All the ones come from this part of the code:

if(lchild <= rchild)
    return rchild + 1;
else
    return lchild + 1;

You add yourself +1 to the results obtained in the leaves of the tree. These ones keep adding up until you exit all the recursive calls of the function and get to the root node.

Improve this answer

Comments

2

Remember in binary trees a node has at most 2 children (left and right)

It is a recursive algorithm, so it calls itself over and over.

If the temp (the node being looked at) is null, it returns 0, as this node is nothing and should not count. that is the base case.

If the node being looked at is not null, it may have children. so it gets the max depth of the left sub tree (and adds 1, for the level of the current node) and the right subtree (and adds 1 for the level of the current node). it then compares the two and returns the greater of the two.

It dives down into the two subtrees (temp->left and temp->right) and repeats the operation until it reaches nodes without children. at that point it will call maxDepth on left and right, which will be null and return 0, and then start returning back up the chain of calls.

So if you you have a chain of three nodes (say, root-left1-left2) it will get down to left2 and call maxDepth(left) and maxDepth(right). each of those return 0 (they are null). then it is back at left2. it compares, both are 0, so the greater of the two is of course 0. it returns 0+1. then we are at left1 - repeats, finds that 1 is the greater of its left n right (perhaps they are the same or it has no right child) so it returns 1+1. now we are at root, same thing, it returns 2+1 = 3, which is the depth.

Improve this answer

Comments

2

Because the depth is calculated with previous node+1

Improve this answer

Comments

0

To find Maximum depth in binary tree keep going left and Traveres the tree, basically perform a DFS
or We can find the depth of the binary search tree in three different recursive ways

– using instance variables to record current depth and total depth at every level
– without using instance variables in top-bottom approach
– without using instance variables in bottom-up approach
Improve this answer

Comments

0

The code snippet can be reduced to just:

int maxDepth(Node *root){
    if(root){ return 1 + max( maxDepth(root->left), maxDepth(root->right)); }
    return 0;
}

A good way of looking at this code is from the top down:

What would happen if the BST had no nodes? We would have root = NULL and the function would immediately return an expected depth of 0.

Now suppose the tree was populated with a number of nodes. Starting at the top, the if condition would be true for the root node. We then ask, what is the max depth of the LEFT SUB TREE and the RIGHT SUB TREE by passing the root of those sub trees to maxDepth. Both the LST and the RST of the root are one level deeper than the root, so we must add one to get the depth of the tree at root of the tree passed to the function.

Improve this answer

1 Comment

wrong it would be like int maxDepth(Node *root){ if(root){ return 1 + max( maxDepth(root->left), maxDepth(root->right)); } return -1; }
0

i think this is the right answer

int maxDepth(Node *root){
    if(root){ return 1 + max( maxDepth(root->left), maxDepth(root->right)); }
    return -1;
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.