Check whether a given tree is a Binary Search Tree in Java
In this Java tutorial, we will solve a well-known problem of Tree data structure. Given a tree, we will check whether the given tree is a Binary search tree or not.
Binary Search Tree in Java
A binary tree is a tree which has at most two children of a node. A binary search tree is a binary tree with some special properties:
- The node value must be greater than all the node values in the left subtree.
- The node value must be less than all the node values in the right subtree.
- Both left and right subtrees must also be a binary search tree.
Algorithm of Binary search tree
We will make a recursive function and we call this function for the root node.
For solving this problem we will use the following steps:
- Call the function for the left node.
- Call the function for the right node.
- If the left subtree is not a BST then the tree is not a BST.
- If the right subtree is not a BST then the tree is not a BST.
- And, If node value is less then the max value of the left subtree then the tree is not a BST.
- Also, If the node value is greater than the minimum value of the right subtree the tree is not a BST.
- Else, the tree is a BST.
Program to check whether a given tree is Binary Search Tree in Java
public class BST { public static void main(String[] args) { /* Tree: 50 / \ 10 20 / \ / \ 30 60 70 80 */ TreeNode root = new TreeNode(50); root.left = new TreeNode(10); root.right = new TreeNode(20); root.left.left = new TreeNode(30); root.left.right = new TreeNode(60); root.right.left = new TreeNode(70); root.right.right = new TreeNode(80); System.out.println(isBST(root).isBst); /* Tree: 50 / \ 20 70 / \ / \ 10 30 60 80 */ TreeNode root2 = new TreeNode(50); root2.left = new TreeNode(20); root2.right = new TreeNode(70); root2.left.left = new TreeNode(10); root2.left.right = new TreeNode(30); root2.right.left = new TreeNode(60); root2.right.right = new TreeNode(80); System.out.println(isBST(root2).isBst); } static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; left = null; right = null; } } static class BSTtriplet { boolean isBst; int max; int min; } static BSTtriplet isBST(TreeNode root) { if (root == null) { BSTtriplet br = new BSTtriplet(); br.isBst = true; br.max = Integer.MIN_VALUE; br.min = Integer.MAX_VALUE; return br; } BSTtriplet lr = isBST(root.left); BSTtriplet rr = isBST(root.right); BSTtriplet myRes = new BSTtriplet(); if (!lr.isBst || !rr.isBst || root.val < lr.max || root.val > rr.min) { myRes.isBst = false; } else { myRes.isBst = true; } myRes.min = Math.min(root.val, Math.min(lr.min, rr.min)); myRes.max = Math.max(root.val, Math.max(lr.max, rr.max)); return myRes; } }
Output:
false true
You can also read:
Leave a Reply