Skip to content

Commit deef2ae

Browse files
albina-astralbina-astr
authored
Refactor CreateBinaryTreeFromInorderPreorder (TheAlgorithms#4190)
1 parent 0255705 commit deef2ae

File tree

2 files changed

+156
-84
lines changed

2 files changed

+156
-84
lines changed

‎src/main/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorder.java‎

Lines changed: 53 additions & 84 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
package com.thealgorithms.datastructures.trees;
22

33
import com.thealgorithms.datastructures.trees.BinaryTree.Node;
4+
45
import java.util.HashMap;
56
import java.util.Map;
67

@@ -11,104 +12,74 @@
1112
* subtree. Based on that index create left and right subtree. Complexity: Time:
1213
* O(n^2) for each node there is iteration to find index in inorder array Space:
1314
* Stack size = O(height) = O(lg(n))
14-
*
15+
* <p>
1516
* Optimized Solution: Instead of iterating over inorder array to find index of
1617
* root value, create a hashmap and find out the index of root value.
1718
* Complexity: Time: O(n) hashmap reduced iteration to find index in inorder
1819
* array Space: O(n) space taken by hashmap
19-
*
2020
*/
2121
public class CreateBinaryTreeFromInorderPreorder {
22-
23-
public static void main(String[] args) {
24-
test(new Integer[] {}, new Integer[] {}); // empty tree
25-
test(new Integer[] { 1 }, new Integer[] { 1 }); // single node tree
26-
test(new Integer[] { 1, 2, 3, 4 }, new Integer[] { 1, 2, 3, 4 }); // right skewed tree
27-
test(new Integer[] { 1, 2, 3, 4 }, new Integer[] { 4, 3, 2, 1 }); // left skewed tree
28-
test(
29-
new Integer[] { 3, 9, 20, 15, 7 },
30-
new Integer[] { 9, 3, 15, 20, 7 }
31-
); // normal tree
22+
public static Node createTree(final Integer[] preorder, final Integer[] inorder) {
23+
if (preorder == null || inorder == null) {
24+
return null;
25+
}
26+
return createTree(preorder, inorder, 0, 0, inorder.length);
3227
}
3328

34-
private static void test(
35-
final Integer[] preorder,
36-
final Integer[] inorder
37-
) {
38-
System.out.println(
39-
"\n===================================================="
40-
);
41-
System.out.println("Naive Solution...");
42-
BinaryTree root = new BinaryTree(
43-
createTree(preorder, inorder, 0, 0, inorder.length)
44-
);
45-
System.out.println("Preorder Traversal: ");
46-
root.preOrder(root.getRoot());
47-
System.out.println("\nInorder Traversal: ");
48-
root.inOrder(root.getRoot());
49-
System.out.println("\nPostOrder Traversal: ");
50-
root.postOrder(root.getRoot());
51-
52-
Map<Integer, Integer> map = new HashMap<>();
29+
public static Node createTreeOptimized(final Integer[] preorder, final Integer[] inorder) {
30+
if (preorder == null || inorder == null) {
31+
return null;
32+
}
33+
Map<Integer, Integer> inorderMap = new HashMap<>();
5334
for (int i = 0; i < inorder.length; i++) {
54-
map.put(inorder[i], i);
35+
inorderMap.put(inorder[i], i);
5536
}
56-
BinaryTree optimizedRoot = new BinaryTree(
57-
createTreeOptimized(preorder, inorder, 0, 0, inorder.length, map)
58-
);
59-
System.out.println("\n\nOptimized solution...");
60-
System.out.println("Preorder Traversal: ");
61-
optimizedRoot.preOrder(root.getRoot());
62-
System.out.println("\nInorder Traversal: ");
63-
optimizedRoot.inOrder(root.getRoot());
64-
System.out.println("\nPostOrder Traversal: ");
65-
optimizedRoot.postOrder(root.getRoot());
37+
return createTreeOptimized(preorder, inorderMap, 0, 0, inorder.length);
6638
}
6739

6840
private static Node createTree(
69-
final Integer[] preorder,
70-
final Integer[] inorder,
71-
final int preStart,
72-
final int inStart,
73-
final int size
41+
final Integer[] preorder,
42+
final Integer[] inorder,
43+
final int preStart,
44+
final int inStart,
45+
final int size
7446
) {
7547
if (size == 0) {
7648
return null;
7749
}
7850

7951
Node root = new Node(preorder[preStart]);
8052
int i = inStart;
81-
while (preorder[preStart] != inorder[i]) {
53+
while (!preorder[preStart].equals(inorder[i])) {
8254
i++;
8355
}
8456
int leftNodesCount = i - inStart;
8557
int rightNodesCount = size - leftNodesCount - 1;
8658
root.left =
87-
createTree(
88-
preorder,
89-
inorder,
90-
preStart + 1,
91-
inStart,
92-
leftNodesCount
93-
);
59+
createTree(
60+
preorder,
61+
inorder,
62+
preStart + 1,
63+
inStart,
64+
leftNodesCount
65+
);
9466
root.right =
95-
createTree(
96-
preorder,
97-
inorder,
98-
preStart + leftNodesCount + 1,
99-
i + 1,
100-
rightNodesCount
101-
);
67+
createTree(
68+
preorder,
69+
inorder,
70+
preStart + leftNodesCount + 1,
71+
i + 1,
72+
rightNodesCount
73+
);
10274
return root;
10375
}
10476

10577
private static Node createTreeOptimized(
106-
final Integer[] preorder,
107-
final Integer[] inorder,
108-
final int preStart,
109-
final int inStart,
110-
final int size,
111-
final Map<Integer, Integer> inorderMap
78+
final Integer[] preorder,
79+
final Map<Integer, Integer> inorderMap,
80+
final int preStart,
81+
final int inStart,
82+
final int size
11283
) {
11384
if (size == 0) {
11485
return null;
@@ -119,23 +90,21 @@ private static Node createTreeOptimized(
11990
int leftNodesCount = i - inStart;
12091
int rightNodesCount = size - leftNodesCount - 1;
12192
root.left =
122-
createTreeOptimized(
123-
preorder,
124-
inorder,
125-
preStart + 1,
126-
inStart,
127-
leftNodesCount,
128-
inorderMap
129-
);
93+
createTreeOptimized(
94+
preorder,
95+
inorderMap,
96+
preStart + 1,
97+
inStart,
98+
leftNodesCount
99+
);
130100
root.right =
131-
createTreeOptimized(
132-
preorder,
133-
inorder,
134-
preStart + leftNodesCount + 1,
135-
i + 1,
136-
rightNodesCount,
137-
inorderMap
138-
);
101+
createTreeOptimized(
102+
preorder,
103+
inorderMap,
104+
preStart + leftNodesCount + 1,
105+
i + 1,
106+
rightNodesCount
107+
);
139108
return root;
140109
}
141110
}

‎src/test/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorderTest.java‎

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
package com.thealgorithms.datastructures.trees;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
import org.junit.jupiter.api.Test;
5+
6+
import java.util.Arrays;
7+
8+
/**
9+
* @author Albina Gimaletdinova on 14/05/2023
10+
*/
11+
public class CreateBinaryTreeFromInorderPreorderTest {
12+
@Test
13+
public void testOnNullArraysShouldReturnNullTree() {
14+
// when
15+
BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(null, null);
16+
BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(null, null);
17+
18+
// then
19+
Assertions.assertNull(root);
20+
Assertions.assertNull(rootOpt);
21+
}
22+
23+
@Test
24+
public void testOnEmptyArraysShouldCreateNullTree() {
25+
// given
26+
Integer[] preorder = {};
27+
Integer[] inorder = {};
28+
29+
// when
30+
BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
31+
BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
32+
33+
// then
34+
Assertions.assertNull(root);
35+
Assertions.assertNull(rootOpt);
36+
}
37+
38+
@Test
39+
public void testOnSingleNodeTreeShouldCreateCorrectTree() {
40+
// given
41+
Integer[] preorder = {1};
42+
Integer[] inorder = {1};
43+
44+
// when
45+
BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
46+
BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
47+
48+
// then
49+
checkTree(preorder, inorder, root);
50+
checkTree(preorder, inorder, rootOpt);
51+
}
52+
53+
@Test
54+
public void testOnRightSkewedTreeShouldCreateCorrectTree() {
55+
// given
56+
Integer[] preorder = {1, 2, 3, 4};
57+
Integer[] inorder = {1, 2, 3, 4};
58+
59+
// when
60+
BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
61+
BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
62+
63+
// then
64+
checkTree(preorder, inorder, root);
65+
checkTree(preorder, inorder, rootOpt);
66+
}
67+
68+
@Test
69+
public void testOnLeftSkewedTreeShouldCreateCorrectTree() {
70+
// given
71+
Integer[] preorder = {1, 2, 3, 4};
72+
Integer[] inorder = {4, 3, 2, 1};
73+
74+
// when
75+
BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
76+
BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
77+
78+
// then
79+
checkTree(preorder, inorder, root);
80+
checkTree(preorder, inorder, rootOpt);
81+
}
82+
83+
@Test
84+
public void testOnNormalTreeShouldCreateCorrectTree() {
85+
// given
86+
Integer[] preorder = {3, 9, 20, 15, 7};
87+
Integer[] inorder = {9, 3, 15, 20, 7};
88+
89+
// when
90+
BinaryTree.Node root = CreateBinaryTreeFromInorderPreorder.createTree(preorder, inorder);
91+
BinaryTree.Node rootOpt = CreateBinaryTreeFromInorderPreorder.createTreeOptimized(preorder, inorder);
92+
93+
// then
94+
checkTree(preorder, inorder, root);
95+
checkTree(preorder, inorder, rootOpt);
96+
}
97+
98+
private static void checkTree(Integer[] preorder, Integer[] inorder, BinaryTree.Node root) {
99+
Assertions.assertNotNull(root);
100+
Assertions.assertEquals(PreOrderTraversal.iterativePreOrder(root), Arrays.asList(preorder));
101+
Assertions.assertEquals(InorderTraversal.iterativeInorder(root), Arrays.asList(inorder));
102+
}
103+
}

0 commit comments

Comments
 (0)