-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTreeNode.java
More file actions
150 lines (128 loc) · 3.75 KB
/
TreeNode.java
File metadata and controls
150 lines (128 loc) · 3.75 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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package bst;
public class TreeNode {
private Integer data;
private TreeNode left;
private TreeNode right;
public TreeNode(Integer data) {
this.data = data;
}
public TreeNode find(Integer data) {
//Soft Delete, use this line
// if (data == this.data && !isDeleted)
//Otherwise
if (data == this.data)
return this;
if (left != null && data < this.data)
return left.find(data);
if (right != null)
return right.find(data);
return null;
}
public void traverseInOrder() {
if (this.left != null)
this.left.traverseInOrder();
System.out.print(this + " ");
if (this.right != null)
this.right.traverseInOrder();
}
// recursive
public void insert(Integer data) {
if (data >= this.data ) {
if (this.right == null)
this.right = new TreeNode(data);
else
this.right.insert(data);
} else {
if (this.left == null)
this.left = new TreeNode(data);
else
this.left.insert(data);
}
}
// iterative (Need fix issues)
public void insertIterative(Integer target) {
TreeNode ptr = this, prev=null;
boolean left=false; // remember so we don't compare again
while (ptr != null) {
//if (target == ptr.data) throw new IllegalAccessException(); // we expect good data
prev = ptr;
if (target < ptr.data) { ptr = ptr.left; left = true;}
else { ptr = ptr.right; left = false;}
}
TreeNode tmp = new TreeNode(target);
//if (this == null) return tmp;
if (left) prev.left = tmp;
else prev.right = tmp;
//return tmp;
}
public static TreeNode addSorted(int[] data, int start, int end) {
if (end >= start) {
int mid = (start+end)/2;
TreeNode newNode = new TreeNode(data[mid]);
newNode.left = addSorted(data, start, mid-1);
newNode.right = addSorted(data, mid+1, end);
return newNode;
}
return null;
}
public Integer smallest() {
if (this.left == null)
return this.data;
return left.smallest();
}
public Integer largest() {
if (this.right == null)
return this.data;
return right.largest();
}
public boolean isLeaf() {
return this.left == null && this.right == null;
}
public int height() {
if (isLeaf()) return 1;
int left = 0;
int right = 0;
if (this.left != null)
left = this.left.height();
if (this.right != null)
right = this.right.height();
return (left > right) ? (left + 1) : (right + 1);
}
public int numOfLeafNodes() {
if (isLeaf()) return 1;
int leftLeaves = 0;
int rightLeaves = 0;
if (this.left != null)
leftLeaves = left.numOfLeafNodes();
if (this.right != null)
rightLeaves = right.numOfLeafNodes();
return leftLeaves + rightLeaves;
}
//soft delete ONLY
private boolean isDeleted = false;
public boolean isDeleted() {
return isDeleted;
}
public void delete() {
isDeleted = true;
}
public Integer getData() {
return data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
@Override
public String toString() {
return String.valueOf(this.data);
}
}