✅ [C++/Python] 2 Simple Solutions w/ Images and Detailed Explanation | Recursion + Hashmap
\u2714\uFE0F Solution - I (Recursive)\n\nFirst, we need to observe that we cant form exact binary tree with only 1 traversal. \n For eg. inorder = [9,3,15,20,7]
\u2714\uFE0F ***Solution - I (Recursive)***\n\nFirst, we need to observe that we cant form exact binary tree with only 1 traversal. \n* For eg. `inorder = [9,3,15,20,7]`, here we dont know which is the root node of tree and their children. It could start with any node as root and form a valid binary tree. \n* Similarly, `postorder = [9,15,7,20,3]`, here we know `3` is the root node since traversal ended with it, however we are not sure of its children. It could have been all rest nodes on right side as `(root)3 -> 20 -> 7 -> 15 -> 9` or all on left side as `9 <- 15 <- 7 <- 20 <- 3(root)` or any intermediate of these.\n\nBut, when we consider both traversals, we can form a unique tree. Since the postorder traversal ends with root node, we know the root node of tree is last node of `postorder`. At the same time, we can search for that node in `inorder` and we know that the nodes that occur to its left form its left sub-tree and nodes occuring to the right of it form its right sub-tree. We recursively repeat the same process - \n* Next node in the line from last  from `postorder` forms the root node, we search it in `inorder` and see what its left and right subtree are, then recurse for right subtree first, then the left one...until all nodes are traversed.\n\n\n\n\n<table>\n<tr>\n<th>\n<p align=middle><b>Step</b></p>\n</th>\n<th>\n<p align=middle><b>Description</b></p>\n</th>\n</tr>\n<tr></tr>\n<tr>\n<td><img src="https://assets.leetcode.com/users/images/90e76a97-9d03-4d51-b6d5-cb0409a67736_1637459119.542401.png" width=600 /></td>\n<td>The red node-3 denotes current root node</br>The blue nodes on left and right of red node denotes its left & right-subtrees respectively</br>We recursively construct the right subtree and then left subtree</td>\n</tr>\n<tr></tr>\n<tr>\n<td><img src="https://assets.leetcode.com/users/images/86ac3f2b-c0ce-49b7-b537-f87ae555a5dc_1637459304.2370312.png" width=600 /></td>\n<td>We have recursed to form the right subtree of previous root node-3</br>20 is the next node from end in postorder traversal and so it forms the current node</br>Again, the blue nodes on left & right of 20 denote its left & right-subtrees respectively</br>We again recursively construct the right subtree and then left subtree</td>\n</tr>\n<tr></tr>\n<tr>\n<td><img src="https://assets.leetcode.com/users/images/505ebc42-7713-4fa7-9110-ea5edc82fc9c_1637459360.4169023.png" width=600 /></td>\n<td>We have recursed to form the right subtree of previous root node-20</br>7 is next node in postorder which forms current node</br>There are no left and right subtrees for 7</br>So just create node-7 and return</td>\n</tr>\n<tr></tr>\n<tr>\n<td><img src="https://assets.leetcode.com/users/images/c881ffb6-5c85-4e06-a195-e506b30d3272_1637459438.2325265.png" width=600 /></td>\n<td>Now, we recurse from step-2 to form left subtree of root node-20</br>Again, 15 is next node in postorder and it forms the current node</br>Again, there are no left and right subtrees</br> So just create node-15 and return</td>\n</tr>\n<tr></tr>\n<tr>\n<td><img src="https://assets.leetcode.com/users/images/075935ae-9ceb-4c2d-8d72-b9bb530dcbf7_1637459480.7908006.png" width=600 /></td>\n<td>Now, we recurse from step-1 to form left subtree of root node-3</br>9 is the next node in postorder and it forms current node</br>We dont have any left and right subtree for 9</br> So just create node-9 and return</td>\n</tr>\n<tr></tr>\n<tr>\n<td><img src="https://assets.leetcode.com/users/images/2ae430ac-ac5b-4886-a4e8-1859f7e6c7de_1637461160.3626633.png" width=600 /></td>\n<td>All the nodes have been traversed</br>The recursion stops here and we return the final tree</td>\n</tr>\n</table>\n\nSo to summarize the algorithm can be stated as -\n1. We start by initializing `postIdx = n-1`, where `n` is the number of nodes. `postIdx` denotes the index of postorder traversal that we are at. It will give us the root node for each point of recursion\n2. We also initialize `inStart = 0` and `inEnd = n-1` which denotes the current range in `inorder` that the subtree will lie in. \n3. At each recursion, we choose `postorder[postIdx]` as current root node. We search that index of that node in `inorder` as well. Then all nodes to the left of that index (till the previous root) are part of current root\'s left sub-tree and all nodes to the right of it are part of its right sub-tree.\n3. We decrement `postIdx` and recurse to build the right sub-tree and then left sub-tree. \n  **Why right first**? Because postorder goes as `left->right->root` and we are traversing it from end. So we consider in order `root->right->left`)\n 4. The process is continued till all nodes are traversed.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        int n = size(inorder), postIdx = n-1;\n        return build(inorder, postorder, 0, n-1, postIdx);\n    }\n\n    TreeNode* build(vector<int>& in, vector<int>& post, int inStart, int inEnd, int& postIdx) {\n        if(inStart > inEnd) return nullptr;\n        TreeNode* root = new TreeNode(post[postIdx--]);\n        int inIdx = find(begin(in), end(in), root -> val) - begin(in);\n        root -> right = build(in, post, inIdx+1, inEnd, postIdx);\n        root -> left  = build(in, post, inStart, inIdx-1, postIdx);\n        return root;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def buildTree(self, inorder, postorder):\n        self.postIdx = len(postorder)-1\n        def build(inStart, inEnd):\n            if inStart > inEnd: return None\n            root = TreeNode(postorder[self.postIdx])\n            self.postIdx -= 1\n            root.right = build(inorder.index(root.val)+1, inEnd)\n            root.left  = build(inStart, inorder.index(root.val)-1)\n            return root        \n        return build(0, len(inorder)-1)\n```\n\n***Time Complexity :*** **<code>O(N<sup>2</sup>)</code>** where `N` is the number of nodes in the tree. At each recursion, we are choosing `post[postIdx]` and searching it in `inorder`. This may take `O(N)` for each search and we are building a tree with `N` such nodes. So total time complexity is <code>O(N<sup>2</sup>)</code>\n***Space Complexity :*** **<code>O(N)</code>**, required by implicit recursive stack. In worst case of skewed tree, the recursion depth might go upto `N`.\n\n---\n\n\u2714\uFE0F ***Solution - II (Recursive w/ Hashmap)***\n\nIn the previous approach, we had to search a node in the `inorder` array everytime which cost us `O(N)` and led to higher time complexity. However, we can reduce this cost if we maintain a mapping of node\'s value to `inorder` node index in a hashmap. This allows us to fetch index of a node in `inorder` array in `O(1)` time at each recursion.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    unordered_map<int, int> mp;\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        for(int i = 0; i < size(inorder); i++) mp[inorder[i]] = i;\n        int n = size(inorder), postIdx = n-1;\n        return build(inorder, postorder, 0, n-1, postIdx);\n    }\n\n    TreeNode* build(vector<int>& in, vector<int>& post, int inStart, int inEnd, int& postIdx) {\n        if(inStart > inEnd) return nullptr;\n        TreeNode* root = new TreeNode(post[postIdx--]);\n        int inIdx = mp[root -> val];\n        root -> right = build(in, post, inIdx+1, inEnd, postIdx);\n        root -> left  = build(in, post, inStart, inIdx-1, postIdx);\n        return root;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def buildTree(self, inorder, postorder):\n        self.postIdx, mp = len(postorder)-1, {val: idx for idx, val in enumerate(inorder)}\n        def build(inStart, inEnd):\n            if inStart > inEnd: return None\n            root = TreeNode(postorder[self.postIdx])\n            self.postIdx -= 1\n            root.right = build(mp[root.val]+1, inEnd)\n            root.left  = build(inStart, mp[root.val]-1)\n            return root        \n        return build(0, len(inorder)-1)\n```\n\n***Time Complexity :*** `O(N)`, now we can find `inIdx` in `O(1)` time. So the time required to build the tree out of `N` nodes each taking `O(1)` comes out to be `O(N)`\n***Space Complexity :*** `O(N)`, requried by recursive stack and to maintain hashmap.\n\n\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---
[]