Divide and Conquer || Edge Handling || Explanation || Working
Intuition\nWhen we are given two types of traversals of a binary tree, inorder and postorder, and asked to reconstruct the binary tree, the key observation is t
# Intuition\nWhen we are given two types of traversals of a binary tree, `inorder` and `postorder`, and asked to reconstruct the binary tree, the key observation is that:\n- In **postorder** traversal, the **last element** is always the root of the current subtree.\n- In **inorder** traversal, the left subtree elements appear before the root, and the right subtree elements appear after the root.\n\nThus, by repeatedly identifying the root from the `postorder` traversal and using the `inorder` traversal to find the boundary between left and right subtrees, we can recursively construct the entire tree.\n\n# Approach\n### Step-by-Step Breakdown:\n1. **Understanding Inorder and Postorder**:\n   - **Inorder** gives us information about the structure of the tree: elements to the left of the root (in `inorder`) belong to the left subtree, and elements to the right belong to the right subtree.\n   - **Postorder** helps us find the root of the tree or subtree, as the last element in a postorder traversal is always the root of the subtree.\n\n2. **Recursive Tree Construction**:\n   - We begin by taking the last element of the `postorder` array as the root.\n   - Using this root\'s value, we find its index in the `inorder` array. This index divides the `inorder` array into two parts: the left part represents the left subtree, and the right part represents the right subtree.\n   - Using the size of the left subtree (calculated from the `inorder` array), we can then identify the corresponding parts of the `postorder` array for the left and right subtrees.\n   - We recursively repeat this process for both subtrees until the entire tree is built.\n\n3. **Edge Cases**:\n   - **Empty Tree**: If the `inorder` or `postorder` arrays are empty, the tree does not exist, and we return `null`.\n   - **Single Node Tree**: When the tree has only one node, both `inorder` and `postorder` arrays will have one element. The recursive call will immediately construct a tree with one node.\n   - **Invalid Input**: If the input arrays are invalid (e.g., lengths don\u2019t match), our algorithm assumes valid input. In a real-world scenario, we would handle such cases with additional checks.\n\n### Working Example:\nLet\'s consider a simple example:\n- **Inorder**: `[9, 3, 15, 20, 7]`\n- **Postorder**: `[9, 15, 7, 20, 3]`\n\n- The last element of the `postorder` array is `3`, which is the root.\n- In the `inorder` array, `3` is located at index `1`. This divides the `inorder` array into:\n  - Left subtree: `[9]`\n  - Right subtree: `[15, 20, 7]`\n\n- Now, we focus on constructing the left and right subtrees:\n  - For the **left subtree**:\n    - Inorder: `[9]`\n    - Postorder: `[9]`\n    - The root is `9`, and there are no more elements to process, so this subtree is complete.\n  \n  - For the **right subtree**:\n    - Inorder: `[15, 20, 7]`\n    - Postorder: `[15, 7, 20]`\n    - The root is `20`, and we divide again:\n      - Left subtree: `[15]`\n      - Right subtree: `[7]`\n    - We build the left subtree with root `15` and right subtree with root `7`.\n\nIn this way, we can recursively build the entire tree.\n\n# Complexity\n- **Time complexity**: $$O(n)$$\n  - Each element of the `inorder` and `postorder` arrays is processed once to determine the root and its position. Finding the index of the root in the `inorder` array takes constant time with a hash map, so the overall time complexity is linear, $$O(n)$$, where `n` is the number of nodes.\n  \n- **Space complexity**: $$O(n)$$\n  - The space complexity is also $$O(n)$$ due to the space required for the recursive call stack (in the worst case, for a completely unbalanced tree) and the space required to store the hash map for the `inorder` indices.\n\n# Conclusion\nBy leveraging the properties of `inorder` and `postorder` traversals, we can efficiently reconstruct the binary tree in linear time. The key is to use the postorder traversal to identify roots and the inorder traversal to divide subtrees.\n\nThis recursive approach covers edge cases such as empty trees and single-node trees, and works well for both balanced and unbalanced binary trees.\n\n\n# Code\n```java []\nclass Solution {\n    public TreeNode buildHelper(int[] inorder, int ins, int inl, int[] postorder, int posts, int postl, Map<Integer, Integer> index) {\n        if (posts > postl || ins > inl) {\n            return null;\n        }\n        \n        // Last element of postorder is the root of current subtree\n        TreeNode root = new TreeNode(postorder[postl]);\n        \n        // Find the index of the root in inorder traversal\n        int ind = index.get(root.val);\n        \n        // Number of elements in left subtree\n        int x = ind - ins;\n        \n        // Recursively build left and right subtrees\n        root.left = buildHelper(inorder, ins, ind - 1, postorder, posts, posts + x - 1, index);\n        root.right = buildHelper(inorder, ind + 1, inl, postorder, posts + x, postl - 1, index);\n        \n        return root;\n    }\n\n    public TreeNode buildTree(int[] inorder, int[] postorder) {\n        // Map value to index in inorder traversal\n        Map<Integer, Integer> index = new HashMap<>();\n        for (int i = 0; i < inorder.length; i++) {\n            index.put(inorder[i], i);\n        }\n\n        // Build the tree\n        return buildHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, index);\n    }\n}\n```\n``` cpp []\nclass Solution {\npublic:\n    TreeNode* buildHelper(vector<int>& inorder, int ins, int inl, vector<int>& postorder, int posts, int postl, unordered_map<int, int>& index) {\n        if (posts > postl || ins > inl) {\n            return nullptr;\n        }\n\n        // Last element of postorder is the root of current subtree\n        TreeNode* root = new TreeNode(postorder[postl]);\n\n        // Find the index of the root in inorder traversal\n        int ind = index[root->val];\n\n        // Number of elements in the left subtree\n        int x = ind - ins;\n\n        // Recursively build left and right subtrees\n        root->left = buildHelper(inorder, ins, ind - 1, postorder, posts, posts + x - 1, index);\n        root->right = buildHelper(inorder, ind + 1, inl, postorder, posts + x, postl - 1, index);\n\n        return root;\n    }\n\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        // Map value to index in inorder traversal\n        unordered_map<int, int> index;\n        for (int i = 0; i < inorder.size(); i++) {\n            index[inorder[i]] = i;\n        }\n\n        // Build the tree\n        return buildHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, index);\n    }\n};\n```\n``` python []\nclass Solution:\n    def buildHelper(self, inorder, ins, inl, postorder, posts, postl, index):\n        if posts > postl or ins > inl:\n            return None\n        \n        # The last element of postorder is the root of the current subtree\n        root = TreeNode(postorder[postl])\n\n        # Find the index of the root in inorder traversal\n        ind = index[root.val]\n        \n        # Number of nodes in the left subtree\n        x = ind - ins\n\n        # Recursively build the left and right subtrees\n        root.left = self.buildHelper(inorder, ins, ind - 1, postorder, posts, posts + x - 1, index)\n        root.right = self.buildHelper(inorder, ind + 1, inl, postorder, posts + x, postl - 1, index)\n\n        return root\n\n    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n        # Map the values to their indices in inorder traversal\n        index = {val: i for i, val in enumerate(inorder)}\n        \n        # Build the tree using the helper function\n        return self.buildHelper(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1, index)\n```
['Array', 'Hash Table', 'Divide and Conquer', 'Tree', 'Binary Tree', 'C++', 'Java', 'Python3']