CODEWITHSUNDEEP
c++recursiontree
Steven
Steven

Reputation: 19

Checking tree node equal to a value

I'm trying to write a recursive function for an arbitrary binary tree that takes a value and a leaf node and it checks to see if a leaf node has that value. This is roughly what I have right now.

bool tree_eq(value, N* node){
  if (node == nullptr){
    return false;
    }
  else{
    if node->value == value{
      return true;
    }
    else{
      return tree_eq(value, N->left);
      return tree_eq(value, N->right);
    }

I know I can't return two things and that is the part I'm struggling to solve. How do I recursively check the right side and the left side if given a root and not a leaf? Thank you

Upvotes: 0

Views: 1186

Answers (2)

2785528
2785528

Reputation: 5566

When your tree is unsorted, change your ending else clause from

 return tree_eq(value, N->left);
 return tree_eq(value, N->right);

and try to 'Or' these two results, as in

 return (tree_eq(value, N->left) ||
         tree_eq(value, N->right));

If your tree is sorted, you need only dfs down one side or the other, not both.

Note that the '||' will not invoke the right branch if found in left branch.

Upvotes: 2

MichaelCMS
MichaelCMS

Reputation: 4763

You need to know if the node is either in the left side or the right side (doesn't really matter the side), so you can say :

 ...
 else {
    return (tree_eq(value,N->left) || tree_eq(value,N->right) );
 }

These will lead to a depth first search where always the left most branch of nodes is taken into consideration.

Upvotes: 2

Related Questions