| 1 | class TreeNode: |
| 2 | def __init__(self, value): |
| 3 | self.value = value |
| 4 | self.left = None |
| 5 | self.right = None |
| 6 | |
| 1 | 7 | def tree_from_traversals(preorder, inorder): |
| 2 | | pass |
| 8 | # Edge Case: Handle None inputs |
| 9 | if preorder is None or inorder is None: |
| 10 | raise ValueError("traversals must have the same length") |
| 11 | |
| 12 | # Edge Case: Handle empty traversals |
| 13 | if len(preorder) == 0 and len(inorder) == 0: |
| 14 | return {} |
| 15 | |
| 16 | # Edge Case: Handle mismatched traversal lengths |
| 17 | if len(preorder) != len(inorder): |
| 18 | raise ValueError("traversals must have the same length") |
| 19 | |
| 20 | # Edge Case: Handle non-unique elements in traversals |
| 21 | if len(preorder) != len(set(preorder)) or len(inorder) != len(set(inorder)): |
| 22 | raise ValueError("traversals must contain unique items") |
| 23 | |
| 24 | # Edge Case: Handle traversals with different elements |
| 25 | if set(preorder) != set(inorder): |
| 26 | raise ValueError("traversals must have the same elements") |
| 27 | |
| 28 | # Base case: empty traversals |
| 29 | if not preorder: |
| 30 | return {} |
| 31 | |
| 32 | # Build the tree recursively |
| 33 | def build_tree(pre_start, pre_end, in_start, in_end): |
| 34 | # Base case |
| 35 | if pre_start > pre_end or in_start > in_end: |
| 36 | return None |
| 37 | |
| 38 | # The first element in preorder is the root |
| 39 | root_value = preorder[pre_start] |
| 40 | root = TreeNode(root_value) |
| 41 | |
| 42 | # Find root position in inorder |
| 43 | root_index = inorder.index(root_value) |
| 44 | |
| 45 | # Calculate sizes of left and right subtrees |
| 46 | left_size = root_index - in_start |
| 47 | |
| 48 | # Recursively build left and right subtrees |
| 49 | root.left = build_tree(pre_start + 1, pre_start + left_size, in_start, root_index - 1) |
| 50 | root.right = build_tree(pre_start + left_size + 1, pre_end, root_index + 1, in_end) |
| 51 | |
| 52 | return root |
| 53 | |
| 54 | # Build the tree |
| 55 | root = build_tree(0, len(preorder) - 1, 0, len(inorder) - 1) |
| 56 | |
| 57 | # Convert tree to dictionary representation |
| 58 | def tree_to_dict(node): |
| 59 | if node is None: |
| 60 | return {} |
| 61 | return { |
| 62 | 'v': node.value, |
| 63 | 'l': tree_to_dict(node.left), |
| 64 | 'r': tree_to_dict(node.right) |
| 65 | } |
| 66 | |
| 67 | return tree_to_dict(root) |
| 68 | # Handled Edge Cases: None inputs, empty traversals, mismatched traversal lengths, non-unique elements, traversals with different elements |