Is This a Binary Search Tree?

Sort by

recency

|

902 Discussions

|

  • + 0 comments

    My Java 8 Solution

    boolean checkBST(Node root) {
            return isBST(root, null, null);
        }
    
        boolean isBST(Node root, Integer min, Integer max) {
            if (root == null) {
                return true;
            }
            
            if ((min != null && root.data <= min) || (max != null && root.data >= max)) {
                return false;
            }
            
            return isBST(root.left, min, root.data) && isBST(root.right, root.data, max);
        }
    
  • + 0 comments
    1. traverse the array in tree.
    2. apply the recursive approach
  • + 0 comments
    """ Node is defined as
    class node:
      def __init__(self, data):
          self.data = data
          self.left = None
          self.right = None
    """
    
    # Could've used inorder traversal and, every time a node is added to results array, check if it's actually greater than the value prior to it, but decided to use try this approach instead, lol.
    
    def check_binary_search_tree_(root):
        # node, min val in current range, max val in current range. Range updates every time a new node is visited. Given the range values, I can implicitly tell whether I'm moving either to the left or to the right.
        stack = [(root, 0, 10e4)]
    
        while stack:
            current, min_in_range, max_in_range = stack.pop()
            if not (min_in_range < current.data < max_in_range):
                return False
    
            if current.right:
                stack.append((current.right, current.data, max_in_range))
            if current.left:
                stack.append((current.left, min_in_range, current.data))
    
        return True
    
  • + 0 comments
    Initially, I was failing some test cases but then i changed the condition in inorder function to check for >= instead of > and then it worked. This means that if a node has a parent or a child equal to itself then it voilates the BST property. 
    
    bool inorder(Node* root,vector<int>& vec){
        if(!root){
            return true;
        }
        bool l=inorder(root->left,vec);
        if(vec.size() && vec.back()>=root->data){
            return false;
        }
        vec.push_back(root->data);
        bool r=inorder(root->right,vec);
    
        return l && r;
    
    }
    bool checkBST(Node* root) {
        if(!root){
            return false;
        }
        vector<int> vec;
        if(inorder(root,vec)){
            return true;
        }
    
        return false;
    }
    
  • + 0 comments

    Some of the tests are wrong. The following tree is binary search. But it says that it's not. Thank u for wasting my time :( data 3 data left 2 data right 6 data 2 data left 1 data right 4 data 1 data 4 data 6 data left 5 data right 7 data 5 data 7