-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathBinarySearchTree.java
More file actions
100 lines (81 loc) · 1.94 KB
/
BinarySearchTree.java
File metadata and controls
100 lines (81 loc) · 1.94 KB
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
94
95
96
97
98
99
100
package dataStructures;
import java.util.Stack;
import dataStructures.BinaryTree.Node;
// duplication not allowed
public class BinarySearchTree {
Stack<Integer> stack;
private Node root;
public Node getRoot() {
return this.root;
}
public void insert(Node root, Node node) {
if(root == null) {
this.root = node;
return;
}
if(node.value < root.value) {
if(root.left == null)
root.left = node;
else {
insert(root.left, node);
return;
}
} else if(node.value > root.value) {
if(root.right == null)
root.right = node;
else {
insert(root.right, node);
return;
}
}
}
public Node delete(int val) {
return delete(this.root, val);
}
public Node delete(Node root, int val) {
if(root == null)
return root;
else if(val < root.value)
root.left = delete(root.left, val);
else if(val > root.value)
root.right = delete(root.right, val);
else {
// case 1: leaf node
if(root.left == null && root.right == null)
root = null;
// case 2: node has 2 children
else if(root.left != null && root.right != null) {
// find minimum in right subtree/ maximum in left subtree
// copy the value to the targeted node
// delete duplicate from right subtree
Node min = getMin(root.right);
root.value = min.value;
root.right = delete(root.right, min.value);
}
// case 3: node has one child(either left or right)
else {
if(root.left == null) // move to right
root = root.right;
else // move to left
root = root.left;
}
}
return root;
}
public Node getNode(int val) {
return getNode(root, val);
}
public Node getNode(Node root, int val) {
if(root == null || root.value == val)
return root;
if(val < root.value)
return getNode(root.left, val);
else
return getNode(root.right, val);
}
private Node getMin(Node root) {
if(root.left != null)
return getMin(root.left);
return root;
}
}