Question:
How to check whether a binary tree is a BST or not using Java

Summary

Here we will consider three methods ‘minimum’, ‘maximum’, and ‘isBST’ to find whether a binary tree is a binary search tree or not. 


Solution

//User function Template for Java


class Solution

{

    //Function to check whether a Binary Tree is BST or not.

    int minimum(Node root) {

        if(root==null)

            return Integer.MAX_VALUE;

        int res = root.data;

        res = Math.min(res,minimum(root.left));

        res = Math.min(res,minimum(root.right));

        return res;

    }

    int maximum(Node root) {

        if(root==null)

            return Integer.MIN_VALUE;

        int res = root.data;

        res = Math.max(res,maximum(root.left));

        res = Math.max(res,maximum(root.right));

        return res;

    }

    boolean isBST(Node root) {

        if(root==null)

            return true;

        else if(root.left==null && root.right==null)

            return true;

        if(isBST(root.left)==false || isBST(root.right)==false)

            return false;

        int min = maximum(root.left);

        int max = minimum(root.right);

        if(min<root.data && root.data<max)

            return true;

        return false;

        // code here.

    }

}


Explanation

  • It returns an integer if the root is null.MAX_VALUE, signifying that an empty subtree has no minimum value.

  • By comparing the value of the current node with the minimum values derived from its left and right subtrees, it recursively determines the minimum value.

  • maximal technique

  • The maximum value found in the subtree rooted at root is returned by this method, which accepts a Node object root as input.

  • When a binary tree rooted at the root is a binary search tree, then this method accepts a Node object root as input and returns true; otherwise, it returns false.


Suggested blogs:

>How to Delete the Node without Head pointer?

>How to make an Array of distinct digits from a mixed array?

>How to check if undirected graph of nodes is a tree or not using Java

>Finding Nth node from end of linked list: Java

>How to find all the possible unique permutations of the array using Java

>How to find the longest subarray with sum divisible by K using Java

>How to print all the paths from the root with a specified sum using Java

>How to return the sum of subarray with maximum sum

>How to return the subarray indexes from left to right using Java

>How to make count consistent across numbers?



Nisha Patel

Nisha Patel

Submit
0 Answers