CODEWITHSUNDEEP
cdata-structuresbinary-search-tree
Leon
Leon

Reputation: 364

Buggy in 1 variation of program to find height of binary search tree

This implementation to find height of a BST works:

int findHeight1(treeNode_type*root)
{
  if(root==NULL)
      return -1;
   else
   {
      return max(findHeight1(root->left),findHeight1(root->right))+1;
   }
}

But this doesn't:

int findHeight(treeNode_type*root)
{
   if( root->left==NULL && root->right==NULL)//current node on stack frame is leaf node
      return 0;
   else
   {
      return max(findHeight(root->left),findHeight(root->right))+1;
   }
}

Both implementations' base case logic seems sound to me but why doesn't the latter work.

Trivial,but just in case:

typedef struct treeNode_type treeNode_type;

struct treeNode_type
{
   int data;
   treeNode_type *left;
   treeNode_type *right;
};

Upvotes: 0

Views: 33

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 753615

Transferring comment to answer.

In the second case, when the node is a leaf node, the height of the tree is 1, not 0. Also, the second case doesn't seem to handle the scenario where the left pointer is not null but the right isn't, or vice versa.

You could use:

int findHeight(treeNode_type*root)
{
   if (root == NULL)
      return 0;
   else if (root->left == NULL && root->right == NULL)
      return 1;
   else
   {
      return max(findHeight(root->left), findHeight(root->right)) + 1;
   }
}

It's not clear there's a significant benefit compared to the simpler first version of the code, though this does avoid two recursive calls for leaf nodes. You could add these conditions and tests before the else clause:

   else if (root->left == NULL)
      return findHeight(root->right) + 1;
   else if (root->right == NULL)
      return findHeight(root->left) + 1;

Again, it isn't clear that it will speed up the processing significantly; the extra conditions might even stall the CPU pipeline and slow it down.

Upvotes: 1

Related Questions