Reconstructing Binary Tree from Inorder and Preorder Traversals
buildTree:
This function serves as the cornerstone for reconstructing the binary tree, utilizing the preorder sequence to establish root nodes and the inorder sequence to identify the left and right subtrees relative to each root. By maintaining a global index for preorder traversal, it sequentially picks root nodes, while the inorder index is searched locally within the function to split the tree into subparts. This recursive division allows for the construction of the tree by continuously defining left and right children based on the traversal orders until the entire tree is formed.
1class Node {
2 constructor(value = 0, left = null, right = null) {
3 this.value = value;
4 this.left = null;
5 this.right = null;
6 }
7}
8
9function buildTree(inOrder, preorder, n) {
10 let preIndex = 0;
11 function buildTreeRecursively(start, end) {
12 if (start > end) return null;
13 let node = new Node(preorder[preIndex++]);
14 if (start == end) return node;
15 let inIndex = inorder.indexOf(node.value, start);
16 node.left = buildTreeRecursively(start, inIndex - 1);
17 node.right = buildTreeRecursively(inIndex + 1, end);
18
19 return node;
20 }
21 return buildTreeRecursively(0, n - 1);
22}
23
24function postorderTraversal(root) {
25 let result = [];
26 function traverse(node) {
27 if (node === null) return;
28 traverse(node.left);
29 traverse(node.right);
30 result.push(node.value);
31 }
32 traverse(root);
33 return result;
34}
35
36const inorder = [1, 6, 8, 7];
37const preorder = [1, 6, 7, 8];
38const n = 4;
39const root = buildTree(inorder, preorder, n);
40console.log(postorderTraversal(root));
41