-1

I was doing some exercise on

https://practice.geeksforgeeks.org/problems/height-of-binary-tree/1

Here is the input format that has been used. enter image description here

I see that their implementation has number of nodes traversed and not number of edges. So, I have added 1 to my answer to compensate for that. However, my answer is failing for their input "5 5 N 4 10 N 8 5 N 8 8 N 6", which I don't understand how it can fail. I am having low confidence and want to know if I am doing anything wrong to find out the height of the tree here.

int result1 = 0;
int result2 = 0;
int MyHeight(Node *root)
{
   if(root->left == NULL && root->right == NULL)
   {
       return 0;
   }

   if(root->left)
   {
     //cout<<"Executing root->left = data = "<<root->data<<endl;
     result1 =  MyHeight(root->left) + 1;
     //cout<<"height -left --of .."<<root->data<<" = "<<result1<<endl;
   }
   if(root->right)
   {
     result2 = MyHeight(root->right) + 1;
     //cout<<"right.height of .."<<root->data<<" = "<<result2<<endl;
   }
   if(result1 > result2)
       return result1;
   return result2;
}

int get_Height(Node* root)
{
  // Your code here
  //cout<<"root->data"<<root->data;
  return MyHeight(root);   
}

On what scenario, this implementation can fail? Can you draw a tree in the scenario where it will fail? I have debug it and I can't see what is going wrong there. It sounds like an invalid BST they have but I want to know if my implementation is correct or not. I cannot see that it is wrong actually.

ankur katiyar
  • 101
  • 5
  • 2
    Please don't tag multiple languages, only the language you're actually writing in. – Some programmer dude Sep 08 '21 at 05:40
  • What does "5 5 N 4 10 N 8 5 N 8 8 N 6" mean? The complete problem statement needs to be in the question. Not just a link to an external site - especially one that requires log in. – kaylum Sep 08 '21 at 05:42
  • 1
    As for your problem, have you tried to *debug* your program? For example by drawing up the tree on paper, with squares for nodes and arrows for pointers, and then step through the code in a debugger and do the same modifications you do in the program in the paper (erasing and redrawing arrows or even boxes as needed)? Can help you understand what's going on. – Some programmer dude Sep 08 '21 at 05:42
  • 2
    Actually, using pen and paper *before* you write code is also very helpful to write code that doesn't have errors (or at least fewer errors). And don't write large pieces of code without testing, write only a few lines at a time, building (with extra warnings enable, and that you treat as errors that must be fixed) and then testing. Once the few lines builds and works fine, you write the next few lines. – Some programmer dude Sep 08 '21 at 05:44
  • 4
    Recursion and global variables don't mix well. Learning from a [good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) would be far more useful than geeksforgeeks could ever be. – Lukas-T Sep 08 '21 at 06:16
  • There is no reason for `result1` and `result2` to be global – you need them to have the same values after recursing as they did before, but they won't. Make them local. – molbdnilo Sep 08 '21 at 07:17

1 Answers1

1

Recursion and global variables don't mix well. You keep overriding these globals in each recursive call.

Specifically result2 = MyHeight(root->right) + 1; can override result1, such that it is not height of root->left anymore, but the height of root->right->left. Explaining recursion is quite tricky, better get your debugger out, step through your code and watch how result1 and result2 change.

Global variables should always be used with care and in this case there is no reason to use global variables at all, making result1 and result2 local to MyHeight should fix your problem.

Lukas-T
  • 11,133
  • 3
  • 20
  • 30