CODEWITHSUNDEEP
javarecursiondata-structuresbinary-search-tree
Sonali Gupta
Sonali Gupta

Reputation: 514

Return in case of Recursive call to a method

I have a piece of code that I need insight on, I don't want to know the correct solution of the problem. I just want to know why is my concept failing. So the function is to check if a binary tree is BST or not. I need to return 1 in case it is and 0 otherwise. My code is as below

int isBST(Node root) {
 if(root == null)
  return 1;
 if(root.left!=null) {
  if(root.left.data<root.data)
    isBST(root.left);
  else
   return 0; // line:a
 }
 if(root.right!=null) {
  if(root.right.data<root.data)
    isBST(root.right);
  else
   return 0;
 }
return 1;
}

For this piece, when i have a binary tree as follows:

5
 \
  7
 /
8

I expect it to reach 8 value and break at line:a but it return me 1 instead of 0. Now I know 0 gets returned to the parent calling method. But is it not terminating because I have made isBST call without capturing the return value? Please dont point out if there are anyother bugs.

Upvotes: 0

Views: 121

Answers (3)

Maurice Perry
Maurice Perry

Reputation: 9650

I see the following issues:

  • If (and only if) isBST(root.left) or isBST(root.right) is false, you need to return 0 (btw, why are you not using booleans?) immediately.
  • The condition root.right.data<root.data should be inverted: root.right.data>=root.data.

So here's the modified code (keeping the int return type):

int isBST(Node root) {
 if(root == null)
  return 1;
 if(root.left!=null) {
  if(root.left.data<root.data) {
    if (isBST(root.left) == 0)
      return 0;
  } else
   return 0;
 }
 if(root.right!=null) {
  if(root.right.data>=root.data) {
    if (isBST(root.right) == 0) {
      return 0;
    }
  } else
   return 0;
 }
return 1;
}

Upvotes: 0

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236084

For the general case, your approach won't work. The way to test if a tree is a BST is to recursively check if the current node is greater than the maximum element of the left subtree, and smaller than the minimum element of the right subtree. Also, you're missing the returns in the recursive calls:

return isBST(root.left);
...
return isBST(root.right);

By the way, why are you returning 0 or 1 for this? use false or true instead, changing the return type to boolean.

Upvotes: 2

JensK
JensK

Reputation: 71

You should check if the right data ist bigger than the current and return the value of the recursive call

if(root.right.data>root.data)

Upvotes: 2

Related Questions