How do you validate a binary search tree?

Question

I read on here of an exercise in interviews known as validating a binary search tree.

How exactly does this work? What would one be looking for in validating a binary search tree? I have written a basic search tree, but never heard of this concept.

Answer 1

Actually that is the mistake everybody does in an interview.

Leftchild must be checked against (minLimitof node,node.value)

Rightchild must be checked against (node.value,MaxLimit of node)

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
         return true;
     if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

Another solution (if space is not a constraint): Do an inorder traversal of the tree and store the node values in an array. If the array is in sorted order, its a valid BST otherwise not.

Answer 2

"Validating" a binary search tree means that you check that it does indeed have all smaller items on the left and large items on the right. Essentially, it's a check to see if a binary tree is a binary search tree.

Answer 3

The best solution I found is O(n) and it uses no extra space. It is similar to inorder traversal but instead of storing it to array and then checking whether it is sorted we can take a static variable and check while inorder traversing whether array is sorted.

static struct node *prev = NULL;

bool isBST(struct node* root)
{
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;

        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
          return false;

        prev = root;

        return isBST(root->right);
    }

    return true;
}

Answer 4

Iterative solution using inorder traversal.

bool is_bst(Node *root) {
  if (!root)
    return true;

  std::stack<Node*> stack;
  bool started = false;
  Node *node = root;
  int prev_val;

  while(true) {
    if (node) {
      stack.push(node);
      node = node->left();
      continue;
    }
    if (stack.empty())
      break;
    node = stack.top();
    stack.pop();

    /* beginning of bst check */
    if(!started) {
      prev_val = node->val();
      started = true;
    } else {
      if (prev_val > node->val())
        return false;
      prev_val = node->val();
    }
    /* end of bst check */

    node = node->right();
  }
  return true;
}

Answer 5

Here is my solution in Clojure:

(defstruct BST :val :left :right)

(defn in-order [bst]
  (when-let [{:keys [val, left, right]} bst]
    (lazy-seq
      (concat (in-order left) (list val) (in-order right)))))

(defn is-strictly-sorted? [col]
  (every?
    (fn [[a b]] (< a  b))
    (partition 2 1 col)))

(defn is-valid-BST [bst]
  (is-strictly-sorted? (in-order bst)))

Answer 6

Since the in-order traversal of a BST is a non-decrease sequence, we could use this property to judge whether a binary tree is BST or not. Using Morris traversal and maintaining the pre node, we could get a solution in O(n) time and O(1) space complexity. Here is my code

public boolean isValidBST(TreeNode root) {
    TreeNode pre = null, cur = root, tmp;
    while(cur != null) {
        if(cur.left == null) {
            if(pre != null && pre.val >= cur.val) 
                return false;
            pre = cur;
            cur = cur.right;
        }
        else {
            tmp = cur.left;
            while(tmp.right != null && tmp.right != cur)
                tmp = tmp.right;
            if(tmp.right == null) { // left child has not been visited
                tmp.right = cur;
                cur = cur.left;
            }
            else { // left child has been visited already
                tmp.right = null;
                if(pre != null && pre.val >= cur.val) 
                    return false;
                pre = cur;
                cur = cur.right;
            }
        }
    }
    return true;
}

Answer 7

Here is my answer in python, it has all the corner cases addressed and well tested in hackerrank website

""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

def checkBST(root):
    return checkLeftSubTree(root, root.left) and checkRightSubTree(root, root.right)

def checkLeftSubTree(root, subTree):
    if not subTree:
        return True
    else:
        return root.data > subTree.data \
        and checkLeftSubTree(root, subTree.left) \ 
        and checkLeftSubTree(root, subTree.right) \
        and checkLeftSubTree(subTree, subTree.left) \
        and checkRightSubTree(subTree, subTree.right)

def checkRightSubTree(root, subTree):
    if not subTree:
        return True
    else:
        return root.data < subTree.data \ 
        and checkRightSubTree(root, subTree.left) \
        and checkRightSubTree(root, subTree.right) \
        and checkRightSubTree(subTree, subTree.right) \
        and checkLeftSubTree(subTree, subTree.left)

Answer 8

bool BinarySearchTree::validate() {
    int minVal = -1;
    int maxVal = -1;
    return ValidateImpl(root, minVal, maxVal);
}

bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal)
{
    int leftMin = -1;
    int leftMax = -1;
    int rightMin = -1;
    int rightMax = -1;

    if (currRoot == NULL) return true;

    if (currRoot->left) {
        if (currRoot->left->value < currRoot->value) {
            if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false;
            if (leftMax != currRoot->left->value && currRoot->value < leftMax)  return false;
        }
        else
            return false;
    } else {
        leftMin = leftMax = currRoot->value;
    }

    if (currRoot->right) {
        if (currRoot->right->value > currRoot->value) {
            if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false;
            if (rightMin != currRoot->right->value && currRoot->value > rightMin)  return false;
        }
        else return false;
    } else {
        rightMin = rightMax = currRoot->value;
    }

    minVal = leftMin < rightMin ? leftMin : rightMin;
    maxVal = leftMax > rightMax ? leftMax : rightMax;

    return true;
}

Answer 9

"It's better to define an invariant first. Here the invariant is -- any two sequential elements of the BST in the in-order traversal must be in strictly increasing order of their appearance (can't be equal, always increasing in in-order traversal). So solution can be just a simple in-order traversal with remembering the last visited node and comparison the current node against the last visited one to '<' (or '>')."

Answer 10

bool ValidateBST(Node *pCurrentNode, int nMin = INT_MIN, int nMax = INT_MAX)
{
    return
    (
        pCurrentNode == NULL
    )
    ||
    (
        (
            !pCurrentNode->pLeftNode ||
            (
                pCurrentNode->pLeftNode->value < pCurrentNode->value &&
                pCurrentNode->pLeftNode->value < nMax &&
                ValidateBST(pCurrentNode->pLeftNode, nMin, pCurrentNode->value)
            )
        )
        &&
        (
            !pCurrentNode->pRightNode ||
            (
                pCurrentNode->pRightNode->value > pCurrentNode->value &&
                pCurrentNode->pRightNode->value > nMin &&
                ValidateBST(pCurrentNode->pRightNode, pCurrentNode->value, nMax)
            )
        )
    );
}

Answer 11

I got this question in a phone interview recently and struggled with it more than I should have. I was trying to keep track of minimums and maximums in child nodes and I just couldn't wrap my brain around the different cases under the pressure of an interview.

After thinking about it while falling asleep last night, I realized that it is as simple as keeping track of the last node you've visited during an inorder traversal. In Java:

public <T extends Comparable<T>> boolean isBst(TreeNode<T> root) {
    return isBst(root, null);
}

private <T extends Comparable<T>> boolean isBst(TreeNode<T> node, TreeNode<T> prev) {
    if (node == null)
        return true;

    if (isBst(node.left, prev) && (prev == null || prev.compareTo(node) < 0 ))
        return isBst(node.right, node);

    return false;
}

Answer 12

In Java and allowing nodes with same value in either sub-tree:

public boolean isValid(Node node) {
    return isValid(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isValid(Node node, int minLimit, int maxLimit) {
    if (node == null)
        return true;
    return minLimit <= node.value && node.value <= maxLimit
            && isValid(node.left, minLimit, node.value)
            && isValid(node.right, node.value, maxLimit);
}

Answer 13

// using inorder traverse based Impl
bool BinarySearchTree::validate() {
    int val = -1;
    return ValidateImpl(root, val);
}

// inorder traverse based Impl
bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) {
    if (currRoot == NULL) return true;

    if (currRoot->left) {
        if (currRoot->left->value > currRoot->value) return false;
        if(!ValidateImpl(currRoot->left, val)) return false;
    }

    if (val > currRoot->value) return false;
    val = currRoot->value;

    if (currRoot->right) {
        if (currRoot->right->value < currRoot->value) return false;
        if(!ValidateImpl(currRoot->right, val)) return false;
    }
    return true;
}

Answer 14

To find out whether given BT is BST for any datatype, you need go with below approach. 1. call recursive function till the end of leaf node using inorder traversal 2. Build your min and max values yourself.

Tree element must have less than / greater than operator defined.

#define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal)
#define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal)

template <class T>
bool IsValidBST (treeNode &root)
{

   T min,  max;
   return IsValidBST (root, &min, &max);
}

template <class T>
bool IsValidBST (treeNode *root, T *MIN , T *MAX)
{
   T leftMin, leftMax, rightMin, rightMax;
   bool isValidBST;

   if (root->leftNode == NULL && root->rightNode == NULL)
   {
      *MIN = root->element;
      *MAX = root->element;
      return true;
   }

  isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax);

  if (isValidBST)
    isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax);

  if (isValidBST)
  {
     *MIN = MIN (leftMIN, rightMIN);
     *Max = MAX (rightMax, leftMax);
  }

  return isValidBST;
}

Answer 15

bool isBST(struct node* root)
{
    static struct node *prev = NULL;
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
            return false;
        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
            return false;
        prev = root;
        return isBST(root->right);
    }
    return true;
}

Works Fine :)

Answer 16

Recursion is easy but iterative approach is better, there is one iterative version above but it's way too complex than necessary. Here is the best solution in c++ you'll ever find anywhere:

This algorithm runs in O(N) time and needs O(lgN) space.

struct TreeNode
{
    int value;
    TreeNode* left;
    TreeNode* right;
};

bool isBST(TreeNode* root) {
    vector<TreeNode*> stack;
    TreeNode* prev = nullptr;
    while (root || stack.size()) {
        if (root) {
           stack.push_back(root);
           root = root->left;
        } else {
            if (prev && stack.back()->value <= prev->value)
                return false;
            prev = stack.back();
            root = prev->right;                    
            stack.pop_back();
        }
    }
    return true;
}

Answer 17

I wrote a solution to use inorder Traversal BST and check whether the nodes is increasing order for space O(1) AND time O(n). TreeNode predecessor is prev node. I am not sure the solution is right or not. Because the inorder Traversal can not define a whole tree.

public boolean isValidBST(TreeNode root, TreeNode predecessor) {
    boolean left = true, right = true;
    if (root.left != null) {
        left = isValidBST(root.left, predecessor);
    }
    if (!left)
        return false;

    if (predecessor.val > root.val)
        return false;

    predecessor.val = root.val;
    if (root.right != null) {
        right = isValidBST(root.right, predecessor);
    }

    if (!right)
        return false;

    return true;

}

Answer 18

Following is the Java implementation of BST validation, where we travel the tree in-order DFS and it returns false if we get any number which is greater than last number.

static class BSTValidator {
  private boolean lastNumberInitialized = false;
  private int lastNumber = -1;

  boolean isValidBST(TreeNode node) {
    if (node.left != null && !isValidBST(node.left)) return false;

    // In-order visiting should never see number less than previous
    // in valid BST.
    if (lastNumberInitialized && (lastNumber > node.getData())) return false;
    if (!lastNumberInitialized) lastNumberInitialized = true;

    lastNumber = node.getData();

    if (node.right != null && !isValidBST(node.right)) return false;

    return true;
  }
}

Answer 19

Recursive solution:

isBinary(root)
    {
        if root == null 
          return true
       else if( root.left == NULL and root.right == NULL)
          return true
       else if(root.left == NULL)
           if(root.right.element > root.element)
               rerturn isBInary(root.right)
        else if (root.left.element < root.element)
              return isBinary(root.left)
        else
              return isBInary(root.left) and isBinary(root.right)

    }

Answer 20

Iterative solution.

private static boolean checkBst(bst node) {

    Stack<bst> s = new Stack<bst>();
    bst temp;
    while(node!=null){
        s.push(node);
        node=node.left;
    }
    while (!s.isEmpty()){
        node = s.pop();
        System.out.println(node.val);
        temp = node;
        if(node.right!=null){
            node = node.right;
            while(node!=null)
            {
                //Checking if the current value is lesser than the previous value and ancestor.
                if(node.val < temp.val)
                    return false;
                if(!s.isEmpty())
                    if(node.val>s.peek().val)
                        return false;
                s.push(node);
                if(node!=null)
                node=node.left;
            }
        }
    }
    return true;
}

Answer 21

This works for duplicates.

// time O(n), space O(logn)
// pseudocode
is-bst(node, min = int.min, max = int.max):
    if node == null:
        return true
    if node.value <= min || max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max)

This works even for int.min and int.max values using Nullable types.

// time O(n), space O(logn)
// pseudocode
is-bst(node, min = null, max = null):
    if node == null:
        return true
    if min != null && node.value <= min
        return false
    if max != null && max < node.value:
        return false
    return is-bst(node.left, min, node.value)
        && is-bst(node.right, node.value, max)

Answer 22

Inspired by http://www.jiuzhang.com/solutions/validate-binary-search-tree/

There are two general solutions: traversal and divide && conquer.

public class validateBinarySearchTree {
    public boolean isValidBST(TreeNode root) {
        return isBSTTraversal(root) && isBSTDivideAndConquer(root);
    }

    // Solution 1: Traversal
    // The inorder sequence of a BST is a sorted ascending list
    private int lastValue = 0; // the init value of it doesn't matter.
    private boolean firstNode = true;
    public boolean isBSTTraversal(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!isValidBST(root.left)) {
            return false;
        }

        // firstNode is needed because of if firstNode is Integer.MIN_VALUE,
        // even if we set lastValue to Integer.MIN_VALUE, it will still return false
        if (!firstNode && lastValue >= root.val) {
            return false;
        }

        firstNode = false;
        lastValue = root.val;

        if (!isValidBST(root.right)) {
            return false;
        }

        return true;

    }

    // Solution 2: divide && conquer
    private class Result {
        int min;
        int max;
        boolean isBST;
        Result(int min, int max, boolean isBST) {
            this.min = min;
            this.max = max;
            this.isBST = isBST;
        }
    }

    public boolean isBSTDivideAndConquer(TreeNode root) {
        return isBSTHelper(root).isBST;
    }

    public Result isBSTHelper(TreeNode root) {
        // For leaf node's left or right
        if (root == null) {
            // we set min to Integer.MAX_VALUE and max to Integer.MIN_VALUE
            // because of in the previous level which is the leaf level,
            // we want to set the min or max to that leaf node's val (in the last return line)
            return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, true);
        }

        Result left = isBSTHelper(root.left);
        Result right = isBSTHelper(root.right);

        if (!left.isBST || !right.isBST) {
            return new Result(0,0, false);
        }

        // For non-leaf node
        if (root.left != null && left.max >= root.val
                && root.right != null && right.min <= root.val) {
            return new Result(0, 0, false);
        }

        return new Result(Math.min(left.min, root.val),
                Math.max(right.max, root.val), true);
    }
}

Answer 23

One liner

bool is_bst(Node *root, int from, int to) {
   return (root == NULL) ? true :
     root->val >= from && root->val <= to &&
     is_bst(root->left, from, root->val) &&
     is_bst(root->right, root->val, to);
}

Pretty long line though.

Answer 24

Here's a solution in java from sedgewick's algorithm class. Check the full BST implementation here

I added some explanatory comments

private boolean isBST() {
    return isBST(root, null, null);

}

private boolean isBST(Node x, Key min, Key max) {
    if (x == null) return true;
    // when checking right subtree min is key of x's parent
    if (min != null && x.key.compareTo(min) <= 0) return false;
    // when checking left subtree, max is key of x's parent
    if (max != null && x.key.compareTo(max) >= 0) return false;
    // check left subtree and right subtree
    return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);

}

Answer 25

• The iterative function checks iteratively whether given tree is a binary search tree.
• The recurse function checks recursively whether given tree is a binary search tree or not.
• In iterative function I use bfs for checking BST.
• In recurse function I use dfs for checking BST.
• Both solutions have a time complexity of O(n)
• iterative solution has an advantage over recurse solution and that is iterative solution does early stopping.
• Even recurse function can be optimized for early stopping by global flag value.
• The idea of both the solution is that the left child should be within the range of -infinity to the value of its parent node whihch is the root node
• The right child should be within the range of +infinity to the value of its parent node whihch is the root node

• And go on comparing the current node's value within the range. If any node's value is not in the range then return False

  class Solution:
      def isValidBST(self, root):
          """
          :type root: TreeNode
          :rtype: bool
          """
          return self.iterative(root)
          # return self.recurse(root, float("inf"), float("-inf"))
  
      def iterative(self, root):
          if not root:
              return True
  
          level = [[root, -float("inf"), float("inf")]]
  
          while level:
              next_level = []
  
              for element in level:
                  node, min_val, max_val = element
                  if min_val<node.val<max_val:
                      if node.left:
                          next_level.append([node.left, min_val, node.val])
                      if node.right:
                          next_level.append([node.right, node.val, max_val])
                  else:
                      return False
              level = next_level
  
          return True
  
      def recurse(self, root, maxi, mini):
          if root is None:
              return True
  
          if root.val < mini or root.val > maxi:
              return False
  
          return self.recurse(root.left, root.val-1, mini) and self.recurse(root.right, maxi, root.val+1)
  

Answer 26

Python implementation example. This example uses type annotations. However since Node class uses itself we need to include as a first line of the module:

from __future__ import annotations

Otherwise, you will get name 'Node' is not defined error. This example also uses dataclass as an example. To check if it's BST it uses recursion for checking left and right nodes values.

"""Checks if Binary Search Tree (BST) is balanced"""

from __future__ import annotations
import sys
from dataclasses import dataclass

MAX_KEY = sys.maxsize
MIN_KEY = -sys.maxsize - 1


@dataclass
class Node:
    value: int
    left: Node
    right: Node

    @property
    def is_leaf(self) -> bool:
        """Check if node is a leaf"""
        return not self.left and not self.right


def is_bst(node: Node, min_value: int, max_value: int) -> bool:
    if node.value < min_value or max_value < node.value:
        return False
    elif node.is_leaf:
        return True

    return is_bst(node.left, min_value, node.value) and is_bst(
        node.right, node.value, max_value
    )


if __name__ == "__main__":
    node5 = Node(5, None, None)
    node25 = Node(25, None, None)
    node40 = Node(40, None, None)
    node10 = Node(10, None, None)

    # balanced tree
    node30 = Node(30, node25, node40)
    root = Node(20, node10, node30)
    print(is_bst(root, MIN_KEY, MAX_KEY))

    # unbalanced tree
    node30 = Node(30, node5, node40)
    root = Node(20, node10, node30)
    print(is_bst(root, MIN_KEY, MAX_KEY))

Answer 27

BST example

    public bool IsBinarySearchTree(TreeNode root)
    {
        return IsValid(root, long.MinValue, long.MaxValue);
    }

    private static bool IsValid(TreeNode node, long min, long max)
    {
        if (node == null)
        {
            return true;
        }

        if (node.Value >= max || node.Value <= min)
        {
            return false;
        }

        return IsValid(node.Left, min, node.Value) && IsValid(node.Right, node.Value, max);
    }

where TreeNode

   public class TreeNode
   {
       public int Value;
       public TreeNode Left;
       public TreeNode Right;

       public TreeNode(int value)
       {
           Value = value;
       }
   }

here's the detailed explanation https://codestandard.net/articles/validate-binary-search-tree/

Answer 28

Here is the iterative solution without using extra space.

Node{
     int value;
     Node right, left
  }

  public boolean ValidateBST(Node root){
    Node currNode = root;
    Node prevNode = null;
    Stack<Node> stack = new Stack<Node>();
    while(true){
        if(currNode != null){
            stack.push(currNode);
            currNode = currNode.left;
            continue;
        }
        if(stack.empty()){
            return;
        }
        currNode = stack.pop();
        if(prevNode != null){
            if(currNode.value < prevNode.value){
                return false;
            }
        }
        prevNode = currNode;
        currNode = currNode.right;
    }
}

Answer 29

 private void validateBinarySearchTree(Node node) {
    if (node == null) return;

    Node left = node.getLeft();
    if (left != null) {
        if (left.getData() < node.getData()) {
            validateBinarySearchTree(left);
        } else {
            throw new IllegalStateException("Not a valid Binary Search tree");
        }
    }

    Node right = node.getRight();
    if (right != null) {
        if (right.getData() > node.getData()) {
            validateBinarySearchTree(right);
        } else {
            throw new IllegalStateException("Not a valid Binary Search tree");
        }
    }
}

Answer 30

boolean isBST(Node root) {
    if (root == null) { return true; }
    return (isBST(root.left) && (isBST(root.right) && (root.left == null || root.left.data <= root.data) && (root.right == null || root.right.data > root.data));
}