FilesExpand file tree

 master

/

ValidBSTOrNot.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

62 lines (53 loc) · 1.65 KB

 master

/

ValidBSTOrNot.java

Top

File metadata and controls

• Code
• Blame

62 lines (53 loc) · 1.65 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

class Node

{

int data;

Node left, right;

public Node(int item)

{

data = item;

left = right = null;

}

}

public class ValidBSTOrNot

{

//Root of the Binary Tree

Node root;

/* can give min and max value according to your code or

can write a function to find min and max value of tree. */

/* returns true if given search tree is binary

search tree (efficient version) */

boolean isBST() {

return isBSTUtil(root, Integer.MIN_VALUE,

Integer.MAX_VALUE);

}

/* Returns true if the given tree is a BST and its

values are >= min and <= max. */

boolean isBSTUtil(Node node, int min, int max)

{

/* an empty tree is BST */

if (node == null)

return true;

/* false if this node violates the min/max constraints */

if (node.data < min || node.data > max)

return false;

/* otherwise check the subtrees recursively

tightening the min/max constraints */

// Allow only distinct values

return (isBSTUtil(node.left, min, node.data-1) &&

isBSTUtil(node.right, node.data+1, max));

}

/* Driver program to test above functions */

public static void main(String args[])

{

ValidBSTOrNot tree = new ValidBSTOrNot();

tree.root = new Node(4);

tree.root.left = new Node(2);

tree.root.right = new Node(5);

tree.root.left.left = new Node(1);

tree.root.left.right = new Node(3);

if (tree.isBST())

System.out.println("IS BST");

else

System.out.println("Not a BST");

}

}