| 9 | 9 | * @returns {Object} |
| 10 | 10 | */ |
| 11 | 11 | export const treeFromTraversals = (preorder, inorder) => { |
| 12 | | throw new Error('Remove this line and implement the function'); |
| 12 | // Edge Case: Empty traversals |
| 13 | if (preorder.length === 0 && inorder.length === 0) { |
| 14 | return {}; |
| 15 | } |
| 16 | |
| 17 | // Edge Case: Different lengths |
| 18 | if (preorder.length !== inorder.length) { |
| 19 | throw new Error('traversals must have the same length'); |
| 20 | } |
| 21 | |
| 22 | // Edge Case: Duplicate items in preorder |
| 23 | if (new Set(preorder).size !== preorder.length) { |
| 24 | throw new Error('traversals must contain unique items'); |
| 25 | } |
| 26 | |
| 27 | // Edge Case: Duplicate items in inorder |
| 28 | if (new Set(inorder).size !== inorder.length) { |
| 29 | throw new Error('traversals must contain unique items'); |
| 30 | } |
| 31 | |
| 32 | // Edge Case: Different elements |
| 33 | const preorderSet = new Set(preorder); |
| 34 | const inorderSet = new Set(inorder); |
| 35 | if (preorder.some(item => !inorderSet.has(item)) || inorder.some(item => !preorderSet.has(item))) { |
| 36 | throw new Error('traversals must have the same elements'); |
| 37 | } |
| 38 | |
| 39 | // Base case for recursion |
| 40 | if (preorder.length === 0) { |
| 41 | return {}; |
| 42 | } |
| 43 | |
| 44 | // Edge Case: Single node tree |
| 45 | if (preorder.length === 1) { |
| 46 | return { value: preorder[0], left: {}, right: {} }; |
| 47 | } |
| 48 | |
| 49 | const root = preorder[0]; |
| 50 | const rootIndexInInorder = inorder.indexOf(root); |
| 51 | |
| 52 | // Edge Case: Invalid traversal sequence (root not found in inorder) |
| 53 | if (rootIndexInInorder === -1) { |
| 54 | throw new Error('traversals must have the same elements'); |
| 55 | } |
| 56 | |
| 57 | const leftInorder = inorder.slice(0, rootIndexInInorder); |
| 58 | const rightInorder = inorder.slice(rootIndexInInorder + 1); |
| 59 | |
| 60 | const leftPreorder = preorder.slice(1, 1 + leftInorder.length); |
| 61 | const rightPreorder = preorder.slice(1 + leftInorder.length); |
| 62 | |
| 63 | const leftSubtree = treeFromTraversals(leftPreorder, leftInorder); |
| 64 | const rightSubtree = treeFromTraversals(rightPreorder, rightInorder); |
| 65 | |
| 66 | return { |
| 67 | value: root, |
| 68 | left: leftSubtree, |
| 69 | right: rightSubtree |
| 70 | }; |
| 13 | 71 | }; |
| 72 | |
| 73 | // Handled Edge Cases: Empty traversals, Different lengths, Duplicate items, Different elements, Single node tree, Invalid traversal sequence |