| 4 | 4 | // |
| 5 | 5 | |
| 6 | 6 | export const treeFromTraversals = (preorder, inorder) => { |
| 7 | | throw new Error('Remove this line and implement the function'); |
| 7 | // Edge Case: Empty traversals |
| 8 | if (preorder.length === 0 && inorder.length === 0) { |
| 9 | return {}; |
| 10 | } |
| 11 | |
| 12 | // Edge Case: Mismatched traversal lengths |
| 13 | if (preorder.length !== inorder.length) { |
| 14 | throw new Error('traversals must have the same length'); |
| 15 | } |
| 16 | |
| 17 | // Edge Case: Duplicate values in traversals |
| 18 | if (new Set(preorder).size !== preorder.length || new Set(inorder).size !== inorder.length) { |
| 19 | throw new Error('traversals must contain unique items'); |
| 20 | } |
| 21 | |
| 22 | // Edge Case: Inconsistent traversals (impossible tree structure) |
| 23 | const preorderSet = new Set(preorder); |
| 24 | const inorderSet = new Set(inorder); |
| 25 | for (const item of preorderSet) { |
| 26 | if (!inorderSet.has(item)) { |
| 27 | throw new Error('traversals must have the same elements'); |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | // Base case: empty traversals |
| 32 | if (preorder.length === 0) { |
| 33 | return {}; |
| 34 | } |
| 35 | |
| 36 | // The first item in preorder is always the root |
| 37 | const root = preorder[0]; |
| 38 | |
| 39 | // Find root position in inorder traversal |
| 40 | const rootIndex = inorder.indexOf(root); |
| 41 | |
| 42 | // Edge Case: Root not found in inorder (should not happen if validation passed, but just in case) |
| 43 | if (rootIndex === -1) { |
| 44 | throw new Error('traversals must have the same elements'); |
| 45 | } |
| 46 | |
| 47 | // Split inorder into left and right subtrees |
| 48 | const leftInorder = inorder.slice(0, rootIndex); |
| 49 | const rightInorder = inorder.slice(rootIndex + 1); |
| 50 | |
| 51 | // Split preorder into left and right subtrees |
| 52 | const leftPreorder = preorder.slice(1, 1 + leftInorder.length); |
| 53 | const rightPreorder = preorder.slice(1 + leftInorder.length); |
| 54 | |
| 55 | // Recursively build left and right subtrees |
| 56 | const leftSubtree = treeFromTraversals(leftPreorder, leftInorder); |
| 57 | const rightSubtree = treeFromTraversals(rightPreorder, rightInorder); |
| 58 | |
| 59 | // Build current node |
| 60 | return { |
| 61 | value: root, |
| 62 | left: leftSubtree, |
| 63 | right: rightSubtree |
| 64 | }; |
| 8 | 65 | }; |
| 66 | |
| 67 | // Handled Edge Cases: Empty traversals, Mismatched traversal lengths, Duplicate values in traversals, Inconsistent traversals (impossible tree structure), Root not found in inorder |