| 1 | 1 | from typing import List, Dict |
| 2 | 2 | |
| 3 | 3 | def tree_from_traversals(preorder: List[str], inorder: List[str]) -> Dict: |
| 4 | | pass |
| 4 | # Edge Case: Handle None inputs |
| 5 | if preorder is None or inorder is None: |
| 6 | raise ValueError("traversals must have the same length") |
| 7 | |
| 8 | # Edge Case: Handle mismatched lengths |
| 9 | if len(preorder) != len(inorder): |
| 10 | raise ValueError("traversals must have the same length") |
| 11 | |
| 12 | # Edge Case: Handle empty traversals |
| 13 | if len(preorder) == 0: |
| 14 | return {} |
| 15 | |
| 16 | # Edge Case: Handle non-unique elements |
| 17 | if len(set(preorder)) != len(preorder) or len(set(inorder)) != len(inorder): |
| 18 | raise ValueError("traversals must contain unique items") |
| 19 | |
| 20 | # Edge Case: Handle traversals with different elements |
| 21 | if set(preorder) != set(inorder): |
| 22 | raise ValueError("traversals must have the same elements") |
| 23 | |
| 24 | # Base case for recursion is handled by the empty traversal check above |
| 25 | |
| 26 | # The first element in preorder is always the root |
| 27 | root = preorder[0] |
| 28 | |
| 29 | # Find the root in inorder traversal to split left and right subtrees |
| 30 | try: |
| 31 | root_index = inorder.index(root) |
| 32 | except ValueError: |
| 33 | # This should not happen due to earlier validation, but included for completeness |
| 34 | raise ValueError("traversals must have the same elements") |
| 35 | |
| 36 | # Split inorder into left and right subtrees |
| 37 | left_inorder = inorder[:root_index] |
| 38 | right_inorder = inorder[root_index + 1:] |
| 39 | |
| 40 | # Split preorder into left and right subtrees |
| 41 | # Left subtree size is the same as left_inorder |
| 42 | left_preorder = preorder[1:1 + len(left_inorder)] |
| 43 | right_preorder = preorder[1 + len(left_inorder):] |
| 44 | |
| 45 | # Recursively build left and right subtrees |
| 46 | left_subtree = tree_from_traversals(left_preorder, left_inorder) |
| 47 | right_subtree = tree_from_traversals(right_preorder, right_inorder) |
| 48 | |
| 49 | # Build the current node |
| 50 | return { |
| 51 | 'v': root, |
| 52 | 'l': left_subtree, |
| 53 | 'r': right_subtree |
| 54 | } |
| 55 | # Handled Edge Cases: None inputs, mismatched lengths, empty traversals, non-unique elements, traversals with different elements |