CODEWITHSUNDEEP
c++recursiontreebinary-treedepth
Ashish Chopra
Ashish Chopra

Reputation: 23

Depth of a node in binary tree

I wrote the following function that returns the depth of a specific node of a binary tree. Consider the tree here: If I ask for the depth of node 5, I should get an answer of 3, from the path 1 -> 2 -> 5.

It's not working; I get 0, even though I return the height from the function.

Here "data" is the value whose depth is to be found, and root is the root node of tree. The initial value of height is 1 (the root node is level 1). 

int height_target(node *root,int data,int height){   if(root==NULL) return 0;

if(root->info==data)
return height;

height_target(root->left,data,height+1);
height_target(root->right,data,height+1);
}

Upvotes: 0

Views: 4717

Answers (6)

kfsone
kfsone

Reputation: 24249

The problem is in your understanding of what return does: it does not terminate all calls to the current function, it only ends the current iteration of said function and passes the value back to the previous stack frame.

Consider:

#include <iostream>

int f(int args) {
    if (args == 3)
        return args;
    f(args + 1);
    std::cout << args << "\n";
}

int main() {
    f(0);
}

http://ideone.com/59Dl7X

Your compiler should have been warning you about the function not returning a value.

What you want is something like this:

static const size_t NODE_NOT_FOUND = 0;

size_t height_target_impl(node *root, int data, size_t height)
{
    if (root == nullptr)
        return NODE_NOT_FOUND;

    if (root->info == data)
        return height;

    int branch_height = height_target_impl(root->left, data, height + 1);
    if (branch_height != NODE_NOT_FOUND)
        return branch_height;
    return height_target_impl(root->right, data, height + 1);
}

size_t height_target(node* root, int data)
{
    return height_target_impl(root, data, 1);
}

Called as:

int h = height_target(root, data);

This returns a value of 0 if the node wasn't found or a 1-based height, with 1 indicating data was found in the root node.

Upvotes: 0

2785528
2785528

Reputation: 5566

It's not working;

Here is one possible fix to your code: (updated - this code now compiles)

Summary - the last two lines of your code discard results during the 'decursion' (when recursion is unravelling). 

int height_target(node* current, int data, int height)
{
   int retVal = 0;

   do {

      if (nullptr == current)
         break;   // 0 indicates not found

      if (current->info == data) { retVal = height;  break; }
      // found the node at 'height'; now de-curse

      retVal = height_target (current->left, data, height+1);
      if (retVal) break; // found data in left branch

      retVal = height_target(current->right, data, height+1);
      if(retVal) break;  // found data in right branch

   }while(0);

   return retVal;
}

Imagine your search item is found 5 layers 'up', so that highest recursion returns 5.

At layer 4, the data was not found, so your code then searched both the left branch and right branch.

With either branch, when your code returned (from layer 5) with the value '5', your code simply discarded the result.

In this possible solution, I tested retVal after return from either left or right. Now if the return value (from layer 5) is not zero, the function will return the non-zero value; eventually popping the value off the stack all the way back 'down' to the bottom of your recursion.

Perhaps a simplified call trace can illustrate:

 height_target (., ., 1);   // first call, data not found at root
 |  height_target (., ., 2);   // recursive call, data not found
 |  |  height_target (., ., 3);   // recurse, not found
 |  |  |  height_target (., ., 4);   // recurse, not found
 |  |  |  |  height_target (., data, 5);   // found! 'decursion' begins
 |  |  |  |  |
 |  |  |  |  returns 5  // height 5 returns 5
 |  |  |  returns 5   // height 4 return 5
 |  |  returns 5   // height 3 returns 5
 |  returns 5   // height 2 returns 5
 returns 5    // height 1 returns 5

First call now returns 5.

Upvotes: 0

Mazzorca
Mazzorca

Reputation: 3

Ok. I think i get it. Try with a function like this:

void height_target(node* root,int data,int height,int& h)
{
  if(root==NULL)
   return;

  if(root->info==data)
   h=height;

  height(root->left,data,height+1,h);
  height(root->right,data,height+1,h);

}

I think you supposend that there can't be two equal values in the tree

Upvotes: 0

Prune
Prune

Reputation: 77847

Most notably, your recursive branch returns nothing. Passing the height back one level isn't enough: you have to pass it all the way up the line.

You need to capture and return the maximum of the left & right subtree calls.

EDIT: remove that last sentence ...

Thus, you need to return the value from whichever call (left or right) finds the desired node. You didn't return anything. Something like:

 ldepth = height_target(root->left , data, height+1);
 if (ldepth > 0)
     return ldepth;
 rdepth = height_target(root->right, data, height+1);
 if (rdepth > 0)
     return rdepth;
 return 0;

This will return whichever branch is successful in finding the desired node, and 0 on failure.

Upvotes: 2

Mazzorca
Mazzorca

Reputation: 3

I think you get 0 as answwer because the condition if(root->info==data)is never satisfied if there isn't a node with value equal to data. If you get 0 as a response it would be that the "data" you search in the binary tree there isn't.

Upvotes: 0

0x5453
0x5453

Reputation: 13589

You aren't doing anything with the value returned from height_target.

Presumably you want something like:

return std::max(height_target(root->left,data,height+1),
                height_target(root->right,data,height+1));

Upvotes: 1

Related Questions