Title: A program to check if a binary tree is BST or not Source: www.geeksforgeeks.org
A binary search tree (BST) is a node based binary tree data structure which has the following properties.
• 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.
From the above properties it naturally follows that:
• Each node (item in the tree) has a distinct key.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/* http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/ */ public class CheckIfBinarySearchTree { public boolean isBinarySearchTree(TreeNode root) { return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } public boolean helper(TreeNode node, int min, int max) { if(node == null) return true; if(node.val < min || node.val > max) return false; return helper(node.left, min, node.val-1) && helper(node.right, node.val+1, max); } public static void main(String args[]) { CheckIfBinarySearchTree c = new CheckIfBinarySearchTree(); //TreeNode root = new TreeNode(4); //root.left = new TreeNode(2); //root.right = new TreeNode(5); //root.left.left = new TreeNode(1); //root.left.right = new TreeNode(3); TreeNode root = new TreeNode(3); root.left = new TreeNode(2); root.right = new TreeNode(5); root.left.left = new TreeNode(1); root.left.right = new TreeNode(4); System.out.println(c.isBinarySearchTree(root)); } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } } |