CODEWITHSUNDEEP
javabinary-search-tree
Andy897
Andy897

Reputation: 7133

Checking if a tree is binary search tree

I am not able to understand how the Java function HERE (Please scroll to the very end of the page) checks if a tree is BST or not, as the code does not look like making using of min and max at all. I am copy pasting the code here as well

/** 
 Tests if a tree meets the conditions to be a 
 binary search tree (BST). Uses the efficient 
 recursive helper. 
*/ 
public boolean isBST2() { 
 return( isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE) ); 
}
/** 
  Efficient BST helper -- Given a node, and min and max values, 
  recurs down the tree to verify that it is a BST, and that all 
  its nodes are within the min..max range. Works in O(n) time -- 
  visits each node only once. 
*/ 
private boolean isBST2(Node node, int min, int max) { 
  if (node==null) { 
    return(true); 
  } 
  else { 
   // left should be in range  min...node.data 
    boolean leftOk = isBST2(node.left, min, node.data);

    // if the left is not ok, bail out 
    if (!leftOk) return(false);

    // right should be in range node.data+1..max 
    boolean rightOk = isBST2(node.right, node.data+1, max);

    return(rightOk); 
  } 
}

Upvotes: 1

Views: 385

Answers (2)

user6519225
user6519225

Reputation: 

boolean checkBST(Node root) {
    return  c(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

boolean c(Node n, int s, int b) {
    return n == null || (n.data > s && n.data < b && c(n.left, s, n.data) && c(n.right, n.data, b));
}

Upvotes: 0

chiastic-security
chiastic-security

Reputation: 20520

A tree is a BST if and only if the nodes of an inorder traversal are monotonic. The easiest way to think of this is that if the root has value n, then the left-hand branch should also be a BST whose nodes are at most n, and the right-hand side should be a BST whose nodes are at least n. If those conditions are satisfied then the tree as a whole is a BST.

That's exactly what your code nearly does. It checks that a tree is a BST with a given minimum a given maximum. It recursively calls itself by looking at the root node with value data, and then checks that the left-hand branch is a BST none of whose nodes exceeds data, and that the right-hand branch is a BST none of whose nodes is smaller than data.

But actually it doesn't quite do this... it misses out the min/max check! Perhaps you're supposed to add that yourself? Is this homework?

The place to add it would be in here:

if (node==null) { 
  return(true); 
}

You just need a couple of extra conditions for if node!=null...

Upvotes: 1

Related Questions