Skip to content

Commit a391ecf

Browse files
marcos-lgmarcos-lg
committed
BAEL-1339 - Implementing a binary tree in Java
1 parent 4e39bfb commit a391ecf

2 files changed

Lines changed: 358 additions & 0 deletions

File tree

‎core-java/src/main/java/com/baeldung/tree/BinaryTree.java‎

Lines changed: 217 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,217 @@
1+
package com.baeldung.tree;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
public class BinaryTree {
7+
8+
Node root;
9+
10+
public void add(int value) {
11+
12+
Node newNode = new Node(value);
13+
14+
if (root == null) {
15+
root = newNode;
16+
return;
17+
}
18+
19+
Node parent = root;
20+
Node current = root;
21+
22+
while (true) {
23+
24+
if (newNode.value < parent.value) {
25+
current = parent.left;
26+
27+
if (current == null) {
28+
parent.left = newNode;
29+
break;
30+
}
31+
} else {
32+
current = parent.right;
33+
34+
if (current == null) {
35+
parent.right = newNode;
36+
break;
37+
}
38+
}
39+
40+
parent = current;
41+
}
42+
43+
}
44+
45+
public boolean isEmpty() {
46+
return root == null;
47+
}
48+
49+
public boolean containsNode(int value) {
50+
51+
Node current = root;
52+
53+
while (current != null) {
54+
55+
if (value == current.value) {
56+
return true;
57+
}
58+
59+
if (value < current.value) {
60+
current = current.left;
61+
} else {
62+
current = current.right;
63+
}
64+
65+
}
66+
67+
return false;
68+
}
69+
70+
public void delete(int value) {
71+
72+
Node current = root;
73+
Node parent = root;
74+
Node nodeToDelete = null;
75+
boolean isLeftChild = false;
76+
77+
while (nodeToDelete == null && current != null) {
78+
79+
if (value == current.value) {
80+
nodeToDelete = current;
81+
} else if (value < current.value) {
82+
parent = current;
83+
current = current.left;
84+
isLeftChild = true;
85+
} else {
86+
parent = current;
87+
current = current.right;
88+
isLeftChild = false;
89+
}
90+
91+
}
92+
93+
if (nodeToDelete == null) {
94+
return;
95+
}
96+
97+
// Case 1: no children
98+
if (nodeToDelete.left == null && nodeToDelete.right == null) {
99+
if (nodeToDelete == root) {
100+
root = null;
101+
} else if (isLeftChild) {
102+
parent.left = null;
103+
} else {
104+
parent.right = null;
105+
}
106+
}
107+
// Case 2: only 1 child
108+
else if (nodeToDelete.right == null) {
109+
if (nodeToDelete == root) {
110+
root = nodeToDelete.left;
111+
} else if (isLeftChild) {
112+
parent.left = nodeToDelete.left;
113+
} else {
114+
parent.right = nodeToDelete.left;
115+
}
116+
} else if (nodeToDelete.left == null) {
117+
if (nodeToDelete == root) {
118+
root = nodeToDelete.right;
119+
} else if (isLeftChild) {
120+
parent.left = nodeToDelete.right;
121+
} else {
122+
parent.right = nodeToDelete.right;
123+
}
124+
}
125+
// Case 3: 2 children
126+
else if (nodeToDelete.left != null && nodeToDelete.right != null) {
127+
Node replacement = findReplacement(nodeToDelete);
128+
if (nodeToDelete == root) {
129+
root = replacement;
130+
} else if (isLeftChild) {
131+
parent.left = replacement;
132+
} else {
133+
parent.right = replacement;
134+
}
135+
}
136+
137+
}
138+
139+
private Node findReplacement(Node nodeToDelete) {
140+
141+
Node replacement = nodeToDelete;
142+
Node parentReplacement = nodeToDelete;
143+
Node current = nodeToDelete.right;
144+
145+
while (current != null) {
146+
parentReplacement = replacement;
147+
replacement = current;
148+
current = current.left;
149+
}
150+
151+
if (replacement != nodeToDelete.right) {
152+
parentReplacement.left = replacement.right;
153+
replacement.right = nodeToDelete.right;
154+
}
155+
156+
replacement.left = nodeToDelete.left;
157+
158+
return replacement;
159+
}
160+
161+
public void traverseInOrder(Node node) {
162+
if (node != null) {
163+
traverseInOrder(node.left);
164+
System.out.print(" " + node.value);
165+
traverseInOrder(node.right);
166+
}
167+
}
168+
169+
public void traversePreOrder(Node node) {
170+
if (node != null) {
171+
System.out.print(" " + node.value);
172+
traversePreOrder(node.left);
173+
traversePreOrder(node.right);
174+
}
175+
}
176+
177+
public void traversePostOrder(Node node) {
178+
if (node != null) {
179+
traversePostOrder(node.left);
180+
traversePostOrder(node.right);
181+
182+
System.out.print(" " + node.value);
183+
}
184+
}
185+
186+
public void traverseLevelOrder() {
187+
Queue<Node> nodes = new LinkedList<>();
188+
nodes.add(root);
189+
190+
while (!nodes.isEmpty()) {
191+
192+
Node node = nodes.remove();
193+
194+
System.out.print(" " + node.value);
195+
196+
if (node.left != null) {
197+
nodes.add(node.left);
198+
}
199+
200+
if (node.left != null) {
201+
nodes.add(node.right);
202+
}
203+
}
204+
}
205+
206+
class Node {
207+
int value;
208+
Node left;
209+
Node right;
210+
211+
Node(int value) {
212+
this.value = value;
213+
right = null;
214+
left = null;
215+
}
216+
}
217+
}

‎core-java/src/test/java/com/baeldung/tree/BinaryTreeTest.java‎

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
package com.baeldung.tree;
2+
3+
import static org.junit.Assert.assertFalse;
4+
import static org.junit.Assert.assertTrue;
5+
6+
import org.junit.Test;
7+
8+
public class BinaryTreeTest {
9+
10+
@Test
11+
public void givenABinaryTree_WhenAddElements_ThenTreeNotEmpty() {
12+
13+
BinaryTree bt = new BinaryTree();
14+
15+
bt.add(6);
16+
bt.add(4);
17+
bt.add(8);
18+
bt.add(3);
19+
bt.add(5);
20+
bt.add(7);
21+
bt.add(9);
22+
23+
assertTrue(!bt.isEmpty());
24+
}
25+
26+
@Test
27+
public void givenABinaryTree_WhenAddElements_ThenTreeContainsThoseElements() {
28+
29+
BinaryTree bt = new BinaryTree();
30+
31+
bt.add(6);
32+
bt.add(4);
33+
bt.add(8);
34+
bt.add(3);
35+
bt.add(5);
36+
bt.add(7);
37+
bt.add(9);
38+
39+
assertTrue(bt.containsNode(6));
40+
assertTrue(bt.containsNode(4));
41+
assertTrue(bt.containsNode(8));
42+
assertTrue(bt.containsNode(3));
43+
assertTrue(bt.containsNode(5));
44+
assertTrue(bt.containsNode(7));
45+
assertTrue(bt.containsNode(9));
46+
47+
assertFalse(bt.containsNode(1));
48+
assertFalse(bt.containsNode(10));
49+
}
50+
51+
@Test
52+
public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {
53+
54+
BinaryTree bt = new BinaryTree();
55+
56+
bt.add(6);
57+
bt.add(4);
58+
bt.add(8);
59+
bt.add(3);
60+
bt.add(5);
61+
bt.add(7);
62+
bt.add(9);
63+
64+
assertTrue(bt.containsNode(9));
65+
bt.delete(9);
66+
assertFalse(bt.containsNode(9));
67+
68+
assertTrue(bt.containsNode(6));
69+
bt.delete(6);
70+
assertFalse(bt.containsNode(6));
71+
72+
assertTrue(bt.containsNode(4));
73+
bt.delete(4);
74+
assertFalse(bt.containsNode(4));
75+
}
76+
77+
@Test
78+
public void givenABinaryTree_WhenTraversingInOrder_ThenPrintValues() {
79+
80+
BinaryTree bt = new BinaryTree();
81+
82+
bt.add(6);
83+
bt.add(4);
84+
bt.add(8);
85+
bt.add(3);
86+
bt.add(5);
87+
bt.add(7);
88+
bt.add(9);
89+
90+
bt.traverseInOrder(bt.root);
91+
}
92+
93+
@Test
94+
public void givenABinaryTree_WhenTraversingPreOrder_ThenPrintValues() {
95+
96+
BinaryTree bt = new BinaryTree();
97+
98+
bt.add(6);
99+
bt.add(4);
100+
bt.add(8);
101+
bt.add(3);
102+
bt.add(5);
103+
bt.add(7);
104+
bt.add(9);
105+
106+
bt.traversePreOrder(bt.root);
107+
}
108+
109+
@Test
110+
public void givenABinaryTree_WhenTraversingPostOrder_ThenPrintValues() {
111+
112+
BinaryTree bt = new BinaryTree();
113+
114+
bt.add(6);
115+
bt.add(4);
116+
bt.add(8);
117+
bt.add(3);
118+
bt.add(5);
119+
bt.add(7);
120+
bt.add(9);
121+
122+
bt.traversePostOrder(bt.root);
123+
}
124+
125+
@Test
126+
public void givenABinaryTree_WhenTraversingLevelOrder_ThenPrintValues() {
127+
128+
BinaryTree bt = new BinaryTree();
129+
130+
bt.add(6);
131+
bt.add(4);
132+
bt.add(8);
133+
bt.add(3);
134+
bt.add(5);
135+
bt.add(7);
136+
bt.add(9);
137+
138+
bt.traverseLevelOrder();
139+
}
140+
141+
}

0 commit comments

Comments
 (0)