FilesExpand file tree

 master

/

ValidBSTOrNot.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

45 lines (36 loc) · 1.22 KB

 master

/

ValidBSTOrNot.java

Copy path

Top

File metadata and controls

• Code
• Blame

45 lines (36 loc) · 1.22 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

package DataStructures.Trees;

public class ValidBSTOrNot {

class Node {

int data;

Node left, right;

public Node(int item) {

data = item;

left = right = null;

}

}

//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));

}

}