JAVA | Detailed explanation ✅
Read till the end:\n---\n\nRole of Postorder traversal: \nTells us which is the root.\n\nRole of Inorder traversal: \nTells us which are the left and right subt
# Read till the end:\n---\n```\nRole of Postorder traversal: \nTells us which is the root.\n\nRole of Inorder traversal: \nTells us which are the left and right subtrees.\n```\nThe root always lie at the end of our postorder array (or subtree subarray). So when we know what our root is, we would want to define the left and right subtree from the inorder array (Becase in inorder, root lies between left and right while in postorder left and right lies together so we don\'t know hwere to put the partition). But we don\'t know where our root lies in the inorder array. So we would use a hashmap to store the inorder elements along with their indices. So we would get the root indices at constant time. \n\nSo in the inorder array:\nLeft subtree would be: `start` to `root index - 1`\nRight subtree would be: `root index + 1` to `end`\n\nIn the postorder array:\nLeft subtree would be: \n`start` to `start + (number of elements in left subtree) - 1`\n\nRight subtree would be:\n`start + (number of elements in left subtree)` to `end`\n\nNow in these broken down subarrays, the root will be given by postorder subarray, and left and right subtree would be derived from inorder subarrays.\n\n(Head over to my YT (in my bio) for a VERY DETAILED explanation. Can\'t share the link coz I was banned from discuss one time).\n\nThe pictures depict how we are defining the subtrees:\n\n![image.png](https://assets.leetcode.com/users/images/08868b1d-1881-476c-a2dd-10c8f284a258_1678971510.0150607.png)\n\n![image.png](https://assets.leetcode.com/users/images/8c24e7ce-ddb5-4a7d-a797-ed5b02f8f003_1678971533.02077.png)\n\n\n\n---\n### Code:\n```\nclass Solution {\n    private Map<Integer, Integer> map;\n    public TreeNode buildTree(int[] inorder, int[] postorder) {\n        map = new HashMap<>();\n        int n = inorder.length;\n        // build the hashmap\n        for (int i = 0; i < n; i++) {\n            map.put(inorder[i], i);\n        }\n        // range is 0 -> n-1 because this is the main function call\n        // for all the elements in the tree\n        return build(inorder, 0, n - 1, postorder, 0, n - 1);\n    }\n\n    // io -> In Order\n    // po -> Post Order\n    private TreeNode build( int[] io, int ioStart, int ioEnd, \n                            int[] po, int poStart, int poEnd) {\n        // BASE CONDITION:\n        // ioStart and ioEnd are moving closer to each, similarly\n        // poStart and poEnd are moving closer to each other \n        // when we\'ll reach the leaf node, \n        // ioStart and ioEnd will be at the same position                          \n        // poStart and poEnd will be at the same position\n        // upon further recursive calls, they\'ll cross each other\n        if (ioStart > ioEnd || poStart > poEnd) {\n            return null;    // in that case return null\n        }\n\n        // po[poEnd] will give us the root node value\n        // because po knows who our root is\n        TreeNode root = new TreeNode(po[poEnd]);    // create the root node\n        // hashmap knows where our root lies in io array\n        int rootIdx = map.get(po[poEnd]);      // get that index from te map\n        // compute the number of elements at the left of root index in io array \n        int numsAtLeft = rootIdx - ioStart;\n        // this numsAtLeft is nothing but the number of elements in our left subtree\n        // We don\'t know from where to where our left and right subtree lies\n        // in the po array, so numsAtLeft will help us \n        // define the range for left and right subtrees in po array\n        // (See the pictures for the parameters in the recursive calls)\n\n        root.left = build(io, ioStart, rootIdx - 1, \n                          po, poStart, poStart + numsAtLeft - 1);\n\n        root.right = build(io, rootIdx + 1, ioEnd, \n                           po, poStart + numsAtLeft, poEnd - 1);\n\n        // our recursion will go to the bottom (single node level) \n        // and build the tree and come back\n        return root;\n    }\n}\n```\n---\n#### Clean solution:\n```\nclass Solution {\n    private Map<Integer, Integer> map = new HashMap<>();\n    public TreeNode buildTree(int[] inorder, int[] postorder) {\n        int n = inorder.length;\n        for (int i = 0; i < n; i++) {\n            map.put(inorder[i], i);\n        }\n\n        return build(inorder, 0, n - 1, postorder, 0, n - 1);\n    }\n\n    private TreeNode build( int[] io, int ioStart, int ioEnd, \n                            int[] po, int poStart, int poEnd) {\n\n        if (ioStart > ioEnd || poStart > poEnd) {\n            return null;    \n        }\n\n        TreeNode root = new TreeNode(po[poEnd]);\n        int rootIdx = map.get(po[poEnd]);      \n        int numsAtLeft = rootIdx - ioStart;\n\n        root.left = build(io, ioStart, rootIdx - 1, \n                          po, poStart, poStart + numsAtLeft - 1);\n\n        root.right = build(io, rootIdx + 1, ioEnd, \n                           po, poStart + numsAtLeft, poEnd - 1);\n        return root;\n    }\n}\n```\n--- \n### Complexity analysis:\n##### Time complexity: $$O(n)$$\n> A $$O(n)$$ to populate the hashmap.\n\n> Another $$O(n)$$ to build the tree, assuming at worst case we build a skewed tree of height $$n$$.\n\n> *We have used a hashmap so that we can access the root indices from the inorder array in constant time. Otherwise we would have had to traverse the ionorder array everytime to get the root index which cost us another $$O(n)$$ time making our tree building process $$O(n^2)$$. So in order to avoid that we used a hashmap.*\n\n> So, final time complexity: $$O(n) + O(n) => O(n)$$ \n\n##### Space complexity: $$O(n)$$\n> We use a hashmap of size $$n$$.\n\n> Our recursive stack space can cost us a space complexity of $$O(n)$$\nassuming we uild a skewed tree of height $$n$$.\n\n> So final time complexity: $$O(n) + O(n) => O(n)$$\n---\n                           Do comment if you have any doubt \uD83D\uDC4D\uD83C\uDFFB\n
['Hash Table', 'Divide and Conquer', 'Tree', 'Binary Tree', 'Java']