CODEWITHSUNDEEP
javarecursionbinary-search-tree
Monica Hübner
Monica Hübner

Reputation: 279

Why the solution for checking the validity of binary tree is not working?

I'm solving a problem to check if a binary tree is valid binary tree. That means the value of the left node of a certain node is smaller and the value of right node is bigger than the node value. The program uses a recursive method to perform the check and return boolean value to determine the validity of the tree. I provided the code as following, 

class Node {

      Node left;
      Node right; 
       int data;

     public Node(int data_ ){

       this.data = data_;
   }
}

public class myTest{


private static List<Integer> lis = new ArrayList<Integer>();

public static List<Integer> inOrder(Node root){

    if (root != null){

        inOrder(root.left);

        lis.add(root.data);
        System.out.println( root.data );
        inOrder(root.right);
    }

    return lis;
}

public static boolean isBST( Node root, int min, int max  ){

    if (root ==  null )
        return true;

    return ( root.data >= min) 
        && ( root.data <= max ) 
        && isBST(root.left, min, root.data) 
        && isBST( root.right, root.data, max );
}

public static void main(String[] args){  

// form the bst
 Node root = new Node(5);
   root.left = new Node(3);
   root.right = new Node(7); 

   root.left.left = new Node(1);
   root.left.right = new Node(2);

   root.right.left = new Node(6);
   root.right.right = new Node(9);

   // get the max and min value from the tree
   int max = 0;
   int min  = 0;

   if (root != null ){

      List<Integer> li  = inOrder(root);
      min =  li.get(0);
      max = li.get( li.size() -1 );
   }


   // determine the validity 
   boolean bol_ = isBST(root, min, max );

   if ( bol_)
     System.out.println("valid BST ");

    else 
        System.out.println("Not valid BST ");
  }

  }

The provided test tree is valid but the program tells it isn't. What is the issue inside that I'm not seeing ? Besides, what will be the edge cases to improve the code ? Say, do I need to check if all the values inside the tree are distinct integer and how to do that ?

Upvotes: 0

Views: 176

Answers (3)

Monica H&#252;bner
Monica H&#252;bner

Reputation: 279

I changed the method little and now it goes as following, 

public static boolean isBST( Node root, int min, int max  ){

    if (root ==  null )
        return true;

    return ( root.data > min) 
        && ( root.data < max ) 
        && isBST(root.left, min, root.data) 
        && isBST( root.right, root.data, max );
}

While the calling is as follow, 

boolean bol_ = isBST(root, min - 1 , max +1 );

Upvotes: 0

Jan Hruby
Jan Hruby

Reputation: 1497

Because of this:

root.left = new Node(3);
root.left.right = new Node(2);

-> on right side there must be value higher then root - like this

root.left = new Node(2);
root.left.right = new Node(3);

Upvotes: 1

Eugen Hotaj
Eugen Hotaj

Reputation: 383

As @Thomas pointed out, your tree is not a valid BST.

However I wanted to give you some advice. There is a lot of edge cases when you are trying to evaluate if a tree is a binary tree or not recursively. One simpler solution would be to traverse the tree in order, store the elements in an ArrayList, then check to see if the list is sorted. This implementation is much easier/simpler and also runs in the same time complexity but with a bigger space complexity: O(n) for both.

Upvotes: 1

Related Questions