FilesExpand file tree

 master

/

BinarySearchTreeImpl.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

93 lines (79 loc) · 1.89 KB

 master

/

BinarySearchTreeImpl.java

Top

File metadata and controls

• Code
• Blame

93 lines (79 loc) · 1.89 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

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

package misc;

/**

* Note:- In BST all the nodes in the left sub-tree of the root node should be

* less than or equals to the data of the root. The data of all the nodes in the

* right subtree of the root node should be greater than the data of the root.

*

*/

public class BinarySearchTreeImpl {

public class BSTNode {

private BSTNode left;

private BSTNode right;

private Integer data;

public BSTNode(Integer data) {

this.data = data;

}

public BSTNode getLeft() {

return left;

}

public void setLeft(BSTNode left) {

this.left = left;

}

public BSTNode getRight() {

return right;

}

public void setRight(BSTNode right) {

this.right = right;

}

public Integer getData() {

return data;

}

}

private BSTNode root;

public boolean isEmpty() {

return (this.root == null);

}

public void insert(Integer data) {

System.out.print("[input: " + data + "]");

if (root == null) {

this.root = new BSTNode(data);

System.out.println(" -> inserted: " + data);

return;

}

insertNode(this.root, data);

System.out.println(" -> inserted: " + data);

System.out.println();

}

private BSTNode insertNode(BSTNode root, Integer data) {

BSTNode tmpNode = null;

System.out.print(" -> " + root.getData());

if (root.getData() >= data) {

System.out.print(" [L]");

if (root.getLeft() == null) {

root.setLeft(new BSTNode(data));

return root.getLeft();

} else {

System.out.println(" [R]");

}

} else {

System.out.print(" [R]");

if (root.getRight() == null) {

root.setRight(new BSTNode(data));

return root.getRight();

} else {

tmpNode = root.getRight();

}

}

return insertNode(tmpNode, data);

}

public static void main(String[] args) {

BinarySearchTreeImpl bst = new BinarySearchTreeImpl();

bst.insert(50);

bst.insert(30);

bst.insert(20);

bst.insert(40);

bst.insert(70);

bst.insert(60);

bst.insert(80);

}

}