🔥Easy Explanation + Video | Java C++ Python
InOrder Traversal: we visit the left subtree first, then the root node, and then the right subtree\n4,10,12,15,18,22,24,25,31,35,44,50,66,70,90\n\nPostOrder Tra
InOrder Traversal: we visit the left subtree first, then the root node, and then the right subtree\n4,10,12,15,18,22,24,25,31,35,44,50,66,70,90\n\nPostOrder Traversal: we visit the left subtree first, then the right subtree, and then the current node\n4,12,10,18,24,22,15,31,44,35,66,90,70,50,25\n\n![image](https://assets.leetcode.com/users/images/6047cd49-5ad5-4a1d-9ed8-228f59c35fc5_1678925849.7006507.jpeg)\n\n# Intuition and Approach\nThe biggest hint is that the root node is always at end in postOrder Traversal ex:  25 is root node.\nWe find this root node in Inorder Traversal and all the elements on left i.e 4,10,12,15,18,22,24 act as left subtree and all elements on right 31,35,44,50,66,70,90 act as right subtree. \n\nThe above process can be repeated to form left and right subtree again individually\neg: 4,10,12,15,18,22,24 is Inorder for left and 4,12,10,18,24,22,15 is Post Order for left and here again 15 will act as the root node. \nHence The idea will be to use Recursion.\n\n# Approach \n1. The buildTree method calls the formBinaryTree method with parameters A, B, 0, A.length-1, 0, and B.length-1. These parameters specify the starting and ending indices of the inorder and postorder traversal arrays.\n2. create a new TreeNode with the last element of the postorder traversal  as the value. This value represents the root node of the current subtree.\n3.  search for this value in the inorder traversal array to find the index of the root node.\n4.   recursively call itself to  form left and right subtree. It passes the parameters as follows:\nfor left:  start, mid-1, start2, x\nfor right: mid+1,end,x+1,end2-1\n\n// x = end of postOrderTraversal of left subtree\nx = no of elemnts in leftSubtree + start of postOrder\n\n# Improvement\nInstead of finding the middle node every time in Inorder Traversal, create a hashMap with value as key and position as value.\n\n<iframe width="560" height="315" src="https://www.youtube.com/embed/2uRa3e3-Vdc" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>\n\n```\nclass Solution {\n    public HashMap<Integer,Integer> hashMap;\n    public TreeNode buildTree(int[] A, int[] B) {\n        hashMap = new HashMap<>();\n        for(int i = 0;i<A.length;i++){\n            hashMap.put(A[i],i);\n        }\n        return formBinaryTree(A,B,0,A.length-1,0,B.length-1);\n    }\n    \n    public TreeNode formBinaryTree(int[] inOrder, int [] postOrder, int start, int end , int start2, int end2)      {\n        if(start > end){\n            \n            return  null;\n        }\n        TreeNode middle = new TreeNode(postOrder[end2]);\n        int mid = hashMap.get(middle.val);\n        \n        int x = mid-1+start2-start;\n        middle.left = formBinaryTree(inOrder,postOrder, start, mid-1, start2, x);\n        middle.right = formBinaryTree(inOrder,postOrder,mid+1,end,x+1,end2-1 );\n        return middle;\n    }\n}\n```\n\n\n```\n\nclass Solution {\n    public TreeNode buildTree(int[] A, int[] B) {\n        return formBinaryTree(A,B,0,A.length-1,0,B.length-1);\n    }\n    \n    public TreeNode formBinaryTree(int[] inOrder, int [] postOrder, int start, int end , int start2, int end2)      {\n        if(start > end){\n            \n            return  null;\n        }\n        TreeNode middle = new TreeNode(postOrder[end2]);\n        int mid = 0;\n        for(int i = start;i<=end;i++){\n            if(inOrder[i]==middle.val) {\n                mid = i;\n                break;\n            }\n        }\n        int noOfElements = mid-1-start;\n        int x = noOfElements + start2;//i.e the end of postOrderTraversal of left subtree\n        middle.left = formBinaryTree(inOrder,postOrder, start, mid-1, start2, x);\n        middle.right = formBinaryTree(inOrder,postOrder,mid+1,end,x+1,end2-1 );\n        return middle;\n    }\n}\n```\n\n```\nclass Solution {\npublic:\n    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {\n        return formBinaryTree(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);\n    }\n\n    TreeNode* formBinaryTree(vector<int>& inOrder, vector<int>& postOrder, int start, int end, int start2, int end2) {\n        if (start > end) {\n            return nullptr;\n        }\n        TreeNode* middle = new TreeNode(postOrder[end2]);\n        int mid = 0;\n        for (int i = start; i <= end; i++) {\n            if (inOrder[i] == middle->val) {\n                mid = i;\n                break;\n            }\n        }\n        int noOfElements = mid - 1 - start;\n        int x = noOfElements + start2; // i.e the end of postOrderTraversal of left subtree\n        middle->left = formBinaryTree(inOrder, postOrder, start, mid - 1, start2, x);\n        middle->right = formBinaryTree(inOrder, postOrder, mid + 1, end, x + 1, end2 - 1);\n        return middle;\n    }\n};\n```\n\n```\n\nclass Solution:\n    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n        return self.formBinaryTree(inorder, postorder, 0, len(inorder) - 1, 0, len(postorder) - 1)\n\n    def formBinaryTree(self, inOrder: List[int], postOrder: List[int], start: int, end: int, start2: int, end2: int) -> TreeNode:\n        if start > end:\n            return None\n        middle = TreeNode(postOrder[end2])\n        mid = 0\n        for i in range(start, end + 1):\n            if inOrder[i] == middle.val:\n                mid = i\n                break\n        noOfElements = mid - 1 - start\n        x = noOfElements + start2  # i.e the end of postOrderTraversal of left subtree\n        middle.left = self.formBinaryTree(inOrder, postOrder, start, mid - 1, start2, x)\n        middle.right = self.formBinaryTree(inOrder, postOrder, mid + 1, end, x + 1, end2 - 1)\n        return middle\n```\n\n\n
['C', 'Python', 'Java', 'Python3']