Validate Binary Search Tree - The Coding Shala

Last Updated: 27-Jan-2021
Home >> Interview Questions >> Validate Binary Search Tree

 In this post, we will learn how to Validate Binary Search Tree and will implement its solution in Java.

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.
Example 1:
    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:
    5
   / \
  1   4
      / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Validate Binary Search Tree Java Program

Approach 1

Using recursion and inorder traversal. We can get the list of nodes in In-Order and InOrder is always in ascending order of value.

Java Program: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inOrder(TreeNode root){
        List<Integer> In = new ArrayList<Integer>();
        if(root == null) return In;
        In.addAll(inOrder(root.left));
        In.add(root.val);
        In.addAll(inOrder(root.right));
        return In;
    }
    
    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        list = inOrder(root);
        for(int i=0; i<list.size()-1;i++){
            if(list.get(i)>=list.get(i+1)) return false;
        }
        return true;
    }
}

Approach 2

Iterative Solution.[Using Stack/dfs]

Java Program: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        Stack<TreeNode> st = new Stack<TreeNode>();
        TreeNode check = null;
        while(root != null || !st.empty()){
            while(root != null){
                st.push(root);
                root = root.left;
            }
            root = st.pop();
            if(check != null && root.val <= check.val) return false;
            check = root;
            root = root.right;
        }
        return true;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Single Number 3 LeetCode Solution - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Java Method Overloading - The Coding Shala