Skip to content

Commit b7fbf83

Browse files
soufiane-cheouatipivovarit
soufiane-cheouati
authored and
pivovarit
committed
Revering tree update (eugenp#6561)
* Add files via upload * Add files via upload * Add files via upload * Add files via upload * Add files via upload
1 parent 871ee3c commit b7fbf83

File tree

3 files changed

+142
-143
lines changed

3 files changed

+142
-143
lines changed

‎algorithms-miscellaneous-2/src/main/java/com/baeldung/algorithms/reversingtree/TreeNode.java‎

Lines changed: 42 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -1,42 +1,42 @@
1-
package com.baeldung.algorithms.reversingtree;
2-
3-
public class TreeNode {
4-
5-
private int value;
6-
private TreeNode rightChild;
7-
private TreeNode leftChild;
8-
9-
public int getValue() {
10-
return value;
11-
}
12-
13-
public void setValue(int value) {
14-
this.value = value;
15-
}
16-
17-
public TreeNode getRightChild() {
18-
return rightChild;
19-
}
20-
21-
public void setRightChild(TreeNode rightChild) {
22-
this.rightChild = rightChild;
23-
}
24-
25-
public TreeNode getLeftChild() {
26-
return leftChild;
27-
}
28-
29-
public void setLeftChild(TreeNode leftChild) {
30-
this.leftChild = leftChild;
31-
}
32-
33-
public TreeNode(int value, TreeNode rightChild, TreeNode leftChild) {
34-
this.value = value;
35-
this.rightChild = rightChild;
36-
this.leftChild = leftChild;
37-
}
38-
39-
public TreeNode(int value) {
40-
this.value = value;
41-
}
42-
}
1+
package com.baeldung.algorithms.reversingtree;
2+
3+
public class TreeNode {
4+
5+
private int value;
6+
private TreeNode rightChild;
7+
private TreeNode leftChild;
8+
9+
public int getValue() {
10+
return value;
11+
}
12+
13+
public void setValue(int value) {
14+
this.value = value;
15+
}
16+
17+
public TreeNode getRightChild() {
18+
return rightChild;
19+
}
20+
21+
public void setRightChild(TreeNode rightChild) {
22+
this.rightChild = rightChild;
23+
}
24+
25+
public TreeNode getLeftChild() {
26+
return leftChild;
27+
}
28+
29+
public void setLeftChild(TreeNode leftChild) {
30+
this.leftChild = leftChild;
31+
}
32+
33+
public TreeNode(int value, TreeNode leftChild, TreeNode rightChild) {
34+
this.value = value;
35+
this.rightChild = rightChild;
36+
this.leftChild = leftChild;
37+
}
38+
39+
public TreeNode(int value) {
40+
this.value = value;
41+
}
42+
}

‎algorithms-miscellaneous-2/src/main/java/com/baeldung/algorithms/reversingtree/TreeReverser.java‎

Lines changed: 53 additions & 68 deletions
Original file line numberDiff line numberDiff line change
@@ -1,68 +1,53 @@
1-
package com.baeldung.algorithms.reversingtree;
2-
3-
import java.util.LinkedList;
4-
5-
public class TreeReverser {
6-
7-
public TreeNode createBinaryTree() {
8-
9-
TreeNode leaf1 = new TreeNode(3);
10-
TreeNode leaf2 = new TreeNode(1);
11-
TreeNode leaf3 = new TreeNode(9);
12-
TreeNode leaf4 = new TreeNode(6);
13-
14-
TreeNode nodeLeft = new TreeNode(2, leaf1, leaf2);
15-
TreeNode nodeRight = new TreeNode(7, leaf3, leaf4);
16-
17-
TreeNode root = new TreeNode(4, nodeRight, nodeLeft);
18-
19-
return root;
20-
}
21-
22-
public void reverseRecursive(TreeNode treeNode) {
23-
if (treeNode == null) {
24-
return;
25-
}
26-
27-
TreeNode temp = treeNode.getLeftChild();
28-
treeNode.setLeftChild(treeNode.getRightChild());
29-
treeNode.setRightChild(temp);
30-
31-
reverseRecursive(treeNode.getLeftChild());
32-
reverseRecursive(treeNode.getRightChild());
33-
}
34-
35-
public void reverseIterative(TreeNode treeNode) {
36-
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
37-
38-
if (treeNode != null) {
39-
queue.add(treeNode);
40-
}
41-
42-
while (!queue.isEmpty()) {
43-
44-
TreeNode node = queue.poll();
45-
if (node.getLeftChild() != null)
46-
queue.add(node.getLeftChild());
47-
if (node.getRightChild() != null)
48-
queue.add(node.getRightChild());
49-
50-
TreeNode temp = node.getLeftChild();
51-
node.setLeftChild(node.getRightChild());
52-
node.setRightChild(temp);
53-
}
54-
}
55-
56-
public String toString(TreeNode root) {
57-
if (root == null) {
58-
return "";
59-
}
60-
61-
StringBuffer buffer = new StringBuffer(String.valueOf(root.getValue())).append(" ");
62-
63-
buffer.append(toString(root.getLeftChild()));
64-
buffer.append(toString(root.getRightChild()));
65-
66-
return buffer.toString();
67-
}
68-
}
1+
package com.baeldung.algorithms.reversingtree;
2+
3+
import java.util.LinkedList;
4+
5+
public class TreeReverser {
6+
7+
public void reverseRecursive(TreeNode treeNode) {
8+
if (treeNode == null) {
9+
return;
10+
}
11+
12+
TreeNode temp = treeNode.getLeftChild();
13+
treeNode.setLeftChild(treeNode.getRightChild());
14+
treeNode.setRightChild(temp);
15+
16+
reverseRecursive(treeNode.getLeftChild());
17+
reverseRecursive(treeNode.getRightChild());
18+
}
19+
20+
public void reverseIterative(TreeNode treeNode) {
21+
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
22+
23+
if (treeNode != null) {
24+
queue.add(treeNode);
25+
}
26+
27+
while (!queue.isEmpty()) {
28+
29+
TreeNode node = queue.poll();
30+
if (node.getLeftChild() != null)
31+
queue.add(node.getLeftChild());
32+
if (node.getRightChild() != null)
33+
queue.add(node.getRightChild());
34+
35+
TreeNode temp = node.getLeftChild();
36+
node.setLeftChild(node.getRightChild());
37+
node.setRightChild(temp);
38+
}
39+
}
40+
41+
public String toString(TreeNode root) {
42+
if (root == null) {
43+
return "";
44+
}
45+
46+
StringBuffer buffer = new StringBuffer(String.valueOf(root.getValue())).append(" ");
47+
48+
buffer.append(toString(root.getLeftChild()));
49+
buffer.append(toString(root.getRightChild()));
50+
51+
return buffer.toString();
52+
}
53+
}

‎algorithms-miscellaneous-2/src/test/java/com/baeldung/algorithms/reversingtree/TreeReverserUnitTest.java‎

Lines changed: 47 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -1,33 +1,47 @@
1-
package com.baeldung.algorithms.reversingtree;
2-
3-
import static org.junit.jupiter.api.Assertions.assertEquals;
4-
5-
import org.junit.jupiter.api.Test;
6-
7-
public class TreeReverserUnitTest {
8-
9-
@Test
10-
public void givenTreeWhenReversingRecursivelyThenReversed() {
11-
TreeReverser reverser = new TreeReverser();
12-
13-
TreeNode treeNode = reverser.createBinaryTree();
14-
15-
reverser.reverseRecursive(treeNode);
16-
17-
assertEquals("4 7 9 6 2 3 1", reverser.toString(treeNode)
18-
.trim());
19-
}
20-
21-
@Test
22-
public void givenTreeWhenReversingIterativelyThenReversed() {
23-
TreeReverser reverser = new TreeReverser();
24-
25-
TreeNode treeNode = reverser.createBinaryTree();
26-
27-
reverser.reverseIterative(treeNode);
28-
29-
assertEquals("4 7 9 6 2 3 1", reverser.toString(treeNode)
30-
.trim());
31-
}
32-
33-
}
1+
package com.baeldung.algorithms.reversingtree;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
5+
import org.junit.jupiter.api.Test;
6+
7+
public class TreeReverserUnitTest {
8+
9+
@Test
10+
public void givenTreeWhenReversingRecursivelyThenReversed() {
11+
TreeReverser reverser = new TreeReverser();
12+
13+
TreeNode treeNode = createBinaryTree();
14+
15+
reverser.reverseRecursive(treeNode);
16+
17+
assertEquals("4 7 9 6 2 3 1", reverser.toString(treeNode)
18+
.trim());
19+
}
20+
21+
@Test
22+
public void givenTreeWhenReversingIterativelyThenReversed() {
23+
TreeReverser reverser = new TreeReverser();
24+
25+
TreeNode treeNode = createBinaryTree();
26+
27+
reverser.reverseIterative(treeNode);
28+
29+
assertEquals("4 7 9 6 2 3 1", reverser.toString(treeNode)
30+
.trim());
31+
}
32+
33+
private TreeNode createBinaryTree() {
34+
35+
TreeNode leaf1 = new TreeNode(1);
36+
TreeNode leaf2 = new TreeNode(3);
37+
TreeNode leaf3 = new TreeNode(6);
38+
TreeNode leaf4 = new TreeNode(9);
39+
40+
TreeNode nodeRight = new TreeNode(7, leaf3, leaf4);
41+
TreeNode nodeLeft = new TreeNode(2, leaf1, leaf2);
42+
43+
TreeNode root = new TreeNode(4, nodeLeft, nodeRight);
44+
45+
return root;
46+
}
47+
}

0 commit comments

Comments
 (0)