Skip to content

Commit e538158

Browse files
mpokryvampokryva
committed
Changed find(int key) method to return null when node is not found, and updated docs accordingly. Issue TheAlgorithms#104.
1 parent 0aee19d commit e538158

1 file changed

Lines changed: 138 additions & 140 deletions

File tree

‎data_structures/Trees/BinaryTree.java‎

Lines changed: 138 additions & 140 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,20 @@
11
/**
2-
* This entire class is used to build a Binary Tree data structure.
3-
* There is the Node Class and the Tree Class, both explained below.
4-
*
5-
* @author Unknown
6-
*
7-
*/
2+
* This entire class is used to build a Binary Tree data structure.
3+
* There is the Node Class and the Tree Class, both explained below.
4+
*
5+
* @author Unknown
6+
*
7+
*/
88

99

1010
/**
11-
* This class implements the nodes that will go on the Binary Tree.
12-
* They consist of the data in them, the node to the left, the node
13-
* to the right, and the parent from which they came from.
14-
*
15-
* @author Unknown
16-
*
17-
*/
11+
* This class implements the nodes that will go on the Binary Tree.
12+
* They consist of the data in them, the node to the left, the node
13+
* to the right, and the parent from which they came from.
14+
*
15+
* @author Unknown
16+
*
17+
*/
1818
class Node{
1919
/** Data for the node */
2020
public int data;
@@ -26,10 +26,10 @@ class Node{
2626
public Node parent;
2727

2828
/**
29-
* Constructor of Node
30-
*
31-
* @param value Value to put in the node
32-
*/
29+
* Constructor of Node
30+
*
31+
* @param value Value to put in the node
32+
*/
3333
public Node(int value){
3434
data = value;
3535
left = null;
@@ -40,56 +40,54 @@ public Node(int value){
4040

4141

4242
/**
43-
* A binary tree is a data structure in which an element
44-
* has two successors(children). The left child is usually
45-
* smaller than the parent, and the right child is usually
46-
* bigger.
47-
*
48-
* @author Unknown
49-
*
50-
*/
43+
* A binary tree is a data structure in which an element
44+
* has two successors(children). The left child is usually
45+
* smaller than the parent, and the right child is usually
46+
* bigger.
47+
*
48+
* @author Unknown
49+
*
50+
*/
5151
class Tree{
5252
/** The root of the Binary Tree */
5353
private Node root;
5454

5555
/**
56-
* Constructor
57-
*/
56+
* Constructor
57+
*/
5858
public Tree(){
5959
root = null;
6060
}
61-
61+
6262
/**
63-
* Method to find a Node with a certain value
64-
*
65-
* @param key Value being looked for
66-
* @return The node if it finds it, otherwise returns the parent
67-
*/
68-
public Node find(int key){
63+
* Method to find a Node with a certain value
64+
*
65+
* @param key Value being looked for
66+
* @return The node if it finds it, otherwise returns the parent
67+
*/
68+
public Node find(int key) {
6969
Node current = root;
70-
Node last = root;
71-
while(current != null){
72-
last = current;
73-
if(key < current.data)
70+
while (current != null) {
71+
if(key < current.data) {
7472
current = current.left;
75-
else if(key > current.data)
73+
} else if(key > current.data) {
7674
current = current.right;
77-
//If you find the value return it
78-
else
75+
} else { // If you find the value return it
7976
return current;
77+
}
8078
}
81-
return last;
79+
return null;
8280
}
8381

8482
/**
85-
* Inserts certain value into the Binary Tree
86-
*
87-
* @param value Value to be inserted
88-
*/
83+
* Inserts certain value into the Binary Tree
84+
*
85+
* @param value Value to be inserted
86+
*/
8987
public void put(int value){
9088
Node newNode = new Node(value);
9189
if(root == null)
92-
root = newNode;
90+
root = newNode;
9391
else{
9492
//This will return the soon to be parent of the value you're inserting
9593
Node parent = find(value);
@@ -109,29 +107,29 @@ public void put(int value){
109107
}
110108

111109
/**
112-
* Deletes a given value from the Binary Tree
113-
*
114-
* @param value Value to be deleted
115-
* @return If the value was deleted
116-
*/
110+
* Deletes a given value from the Binary Tree
111+
*
112+
* @param value Value to be deleted
113+
* @return If the value was deleted
114+
*/
117115
public boolean remove(int value){
118116
//temp is the node to be deleted
119117
Node temp = find(value);
120118

121119
//If the value doesn't exist
122120
if(temp.data != value)
123-
return false;
121+
return false;
124122

125123
//No children
126124
if(temp.right == null && temp.left == null){
127125
if(temp == root)
128-
root = null;
126+
root = null;
129127

130128
//This if/else assigns the new node to be either the left or right child of the parent
131129
else if(temp.parent.data < temp.data)
132-
temp.parent.right = null;
130+
temp.parent.right = null;
133131
else
134-
temp.parent.left = null;
132+
temp.parent.left = null;
135133
return true;
136134
}
137135

@@ -162,9 +160,9 @@ else if(temp.left != null && temp.right != null){
162160

163161
//This if/else assigns the new node to be either the left or right child of the parent
164162
if(temp.parent.data < temp.data)
165-
temp.parent.right = successor;
163+
temp.parent.right = successor;
166164
else
167-
temp.parent.left = successor;
165+
temp.parent.left = successor;
168166
return true;
169167
}
170168
}
@@ -175,96 +173,96 @@ else if(temp.left != null && temp.right != null){
175173
if(temp == root){
176174
root = temp.right; return true;}
177175

178-
temp.right.parent = temp.parent;
176+
temp.right.parent = temp.parent;
179177

180-
//Assigns temp to left or right child
181-
if(temp.data < temp.parent.data)
178+
//Assigns temp to left or right child
179+
if(temp.data < temp.parent.data)
182180
temp.parent.left = temp.right;
183-
else
181+
else
184182
temp.parent.right = temp.right;
185-
return true;
183+
return true;
184+
}
185+
//If it has a left child
186+
else{
187+
if(temp == root){
188+
root = temp.left; return true;}
189+
190+
temp.left.parent = temp.parent;
191+
192+
//Assigns temp to left or right side
193+
if(temp.data < temp.parent.data)
194+
temp.parent.left = temp.left;
195+
else
196+
temp.parent.right = temp.left;
197+
return true;
198+
}
199+
}
186200
}
187-
//If it has a left child
188-
else{
189-
if(temp == root){
190-
root = temp.left; return true;}
191201

192-
temp.left.parent = temp.parent;
202+
/**
203+
* This method finds the Successor to the Node given.
204+
* Move right once and go left down the tree as far as you can
205+
*
206+
* @param n Node that you want to find the Successor of
207+
* @return The Successor of the node
208+
*/
209+
public Node findSuccessor(Node n){
210+
if(n.right == null)
211+
return n;
212+
Node current = n.right;
213+
Node parent = n.right;
214+
while(current != null){
215+
parent = current;
216+
current = current.left;
217+
}
218+
return parent;
219+
}
193220

194-
//Assigns temp to left or right side
195-
if(temp.data < temp.parent.data)
196-
temp.parent.left = temp.left;
197-
else
198-
temp.parent.right = temp.left;
199-
return true;
221+
/**
222+
* Returns the root of the Binary Tree
223+
*
224+
* @return the root of the Binary Tree
225+
*/
226+
public Node getRoot(){
227+
return root;
200228
}
201-
}
202-
}
203229

204-
/**
205-
* This method finds the Successor to the Node given.
206-
* Move right once and go left down the tree as far as you can
207-
*
208-
* @param n Node that you want to find the Successor of
209-
* @return The Successor of the node
210-
*/
211-
public Node findSuccessor(Node n){
212-
if(n.right == null)
213-
return n;
214-
Node current = n.right;
215-
Node parent = n.right;
216-
while(current != null){
217-
parent = current;
218-
current = current.left;
219-
}
220-
return parent;
221-
}
230+
/**
231+
* Prints leftChild - root - rightChild
232+
*
233+
* @param localRoot The local root of the binary tree
234+
*/
235+
public void inOrder(Node localRoot){
236+
if(localRoot != null){
237+
inOrder(localRoot.left);
238+
System.out.print(localRoot.data + " ");
239+
inOrder(localRoot.right);
240+
}
241+
}
222242

223-
/**
224-
* Returns the root of the Binary Tree
225-
*
226-
* @return the root of the Binary Tree
227-
*/
228-
public Node getRoot(){
229-
return root;
230-
}
243+
/**
244+
* Prints root - leftChild - rightChild
245+
*
246+
* @param localRoot The local root of the binary tree
247+
*/
248+
public void preOrder(Node localRoot){
249+
if(localRoot != null){
250+
System.out.print(localRoot.data + " ");
251+
preOrder(localRoot.left);
252+
preOrder(localRoot.right);
253+
}
254+
}
231255

232-
/**
233-
* Prints leftChild - root - rightChild
234-
*
235-
* @param localRoot The local root of the binary tree
236-
*/
237-
public void inOrder(Node localRoot){
238-
if(localRoot != null){
239-
inOrder(localRoot.left);
240-
System.out.print(localRoot.data + " ");
241-
inOrder(localRoot.right);
242-
}
243-
}
244-
245-
/**
246-
* Prints root - leftChild - rightChild
247-
*
248-
* @param localRoot The local root of the binary tree
249-
*/
250-
public void preOrder(Node localRoot){
251-
if(localRoot != null){
252-
System.out.print(localRoot.data + " ");
253-
preOrder(localRoot.left);
254-
preOrder(localRoot.right);
255-
}
256-
}
257-
258-
/**
259-
* Prints rightChild - leftChild - root
260-
*
261-
* @param localRoot The local root of the binary tree
262-
*/
263-
public void postOrder(Node localRoot){
264-
if(localRoot != null){
265-
postOrder(localRoot.left);
266-
postOrder(localRoot.right);
267-
System.out.print(localRoot.data + " ");
256+
/**
257+
* Prints rightChild - leftChild - root
258+
*
259+
* @param localRoot The local root of the binary tree
260+
*/
261+
public void postOrder(Node localRoot){
262+
if(localRoot != null){
263+
postOrder(localRoot.left);
264+
postOrder(localRoot.right);
265+
System.out.print(localRoot.data + " ");
266+
}
267+
}
268268
}
269-
}
270-
}

0 commit comments

Comments
 (0)