Solution For Construct Binary Tree From Inorder And Postorder Traversal
Problem Statement:
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Example:
Inorder traversal: [9,3,15,20,7] Postorder traversal: [9,15,7,20,3]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
Solution Approach:
Inorder traversal follows the left, root, right sequence whereas postorder follows the left, right, root sequence. From the postorder, we can find the root of the tree and then use that to divide the inorder array into left and right subtrees.
We can create a recursive function that takes in the two arrays and builds the tree recursively. The function can start by finding the root from the postorder array and then searching for the root in the inorder array. All elements to the left of the root in the inorder array can be used to build the left subtree and all elements to the right of the root in the inorder array can be used to build the right subtree.
Once the left and right subtrees are built, they can be attached to the root to create the final binary tree. The function can be recursively called with the left and right subtrees to build the complete binary tree.
Solution:
Here’s the Python solution for the problem:
“`
class TreeNode:
def init(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not inorder or not postorder:
return None
root_val = postorder.pop()
root = TreeNode(root_val)
idx = inorder.index(root_val)
root.right = self.buildTree(inorder[idx+1:], postorder)
root.left = self.buildTree(inorder[:idx], postorder)
return root
“`
The above solution has a time complexity of O(n^2) since the index method used on lists with multiple same values takes O(n) time. We can improve the performance by using a hash map to store the index of each element in the inorder array, thus reducing the time complexity to O(n).
Here’s the optimized Python solution:
“`
class TreeNode:
def init(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
inorder_map = {}
for i, val in enumerate(inorder):
inorder_map[val] = i
def helper(inorder, postorder, in_start, in_end, post_start, post_end):
if in_start > in_end or post_start > post_end:
return None
root_val = postorder[post_end]
root = TreeNode(root_val)
idx = inorder_map[root_val]
left_size = idx - in_start
root.left = helper(inorder, postorder, in_start, idx-1, post_start, post_start+left_size-1)
root.right = helper(inorder, postorder, idx+1, in_end, post_start+left_size, post_end-1)
return root
return helper(inorder, postorder, 0, len(inorder)-1, 0, len(postorder)-1)
“`
The above solution has a time complexity of O(n) and a space complexity of O(n).
Step by Step Implementation For Construct Binary Tree From Inorder And Postorder Traversal
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { //edge case if(inorder.length == 0 || postorder.length == 0) return null; //build a hashmap of the inorder array to get the index of each value HashMapmap = new HashMap (); for(int i = 0; i < inorder.length; i++){ map.put(inorder[i], i); } //call the helper function return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, map); } public TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, HashMap map){ //base case if(inStart > inEnd || postStart > postEnd) return null; //get the root from the postorder array int rootValue = postorder[postEnd]; TreeNode root = new TreeNode(rootValue); //get the index of the root from the inorder array int rootIndex = map.get(rootValue); //calculate the number of elements in the left and right subtrees int leftTreeSize = rootIndex - inStart; int rightTreeSize = inEnd - rootIndex; //recursively build the left and right subtrees root.left = buildTreeHelper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftTreeSize - 1, map); root.right = buildTreeHelper(inorder, rootIndex + 1, inEnd, postorder, postEnd - rightTreeSize, postEnd - 1, map); return root; } }
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: # Base case: inorder and postorder are both empty if not inorder and not postorder: return None # Base case: only one element in inorder list if len(inorder) == 1: return TreeNode(inorder[0]) # Find the root of the tree (last element of postorder list) root = TreeNode(postorder[-1]) # Find the index of the root in the inorder list root_index = inorder.index(postorder[-1]) # Slice the inorder and postorder lists around the root to get the left and right subtrees inorder_left = inorder[:root_index] inorder_right = inorder[root_index+1:] postorder_left = postorder[:root_index] postorder_right = postorder[root_index:-1] # Recursively build the left and right subtrees root.left = self.buildTree(inorder_left, postorder_left) root.right = self.buildTree(inorder_right, postorder_right) return root
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[]} inorder * @param {number[]} postorder * @return {TreeNode} */ //Given the inorder and postorder traversal of a binary tree, construct the binary tree. //Note: //You may assume that duplicates do not exist in the tree. //For example, given //inorder = [9,3,15,20,7] //postorder = [9,15,7,20,3] //Return the following binary tree: // 3 // / \ // 9 20 // / \ // 15 7 var buildTree = function(inorder, postorder) { if (!inorder.length || !postorder.length) return null; let val = postorder.pop(); let root = new TreeNode(val); let index = inorder.indexOf(val); root.right = buildTree(inorder.slice(index + 1), postorder.slice(index)); root.left = buildTree(inorder.slice(0, index), postorder.slice(0, index)); return root; };
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* buildTree(vector& inorder, vector & postorder) { // Base case if (inorder.size() == 0 || postorder.size() == 0) { return NULL; } // Create a hashmap of the inorder traversal unordered_map inorderMap; for (int i = 0; i < inorder.size(); i++) { inorderMap[inorder[i]] = i; } // Helper function return buildTreeHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorderMap); } TreeNode* buildTreeHelper(vector & inorder, int inStart, int inEnd, vector & postorder, int postStart, int postEnd, unordered_map & inorderMap) { // Base case if (inStart > inEnd || postStart > postEnd) { return NULL; } // Get the root node from the postorder traversal and create the root int rootVal = postorder[postEnd]; TreeNode* root = new TreeNode(rootVal); // Get the index of the root node in the inorder traversal int rootIndex = inorderMap[rootVal]; // Recursively build the left and right subtrees int leftInStart = inStart; int leftInEnd = rootIndex - 1; int leftPostStart = postStart; int leftPostEnd = leftPostStart + leftInEnd - leftInStart; int rightInStart = rootIndex + 1; int rightInEnd = inEnd; int rightPostStart = leftPostEnd + 1; int rightPostEnd = postEnd - 1; root->left = buildTreeHelper(inorder, leftInStart, leftInEnd, postorder, leftPostStart, leftPostEnd, inorderMap); root->right = buildTreeHelper(inorder, rightInStart, rightInEnd, postorder, rightPostStart, rightPostEnd, inorderMap); return root; } };
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode BuildTree(int[] inorder, int[] postorder) { //Check for invalid inputs if(inorder == null || postorder == null || inorder.Length != postorder.Length) { return null; } return BuildTreeHelper(inorder, postorder, 0, inorder.Length - 1, 0, postorder.Length - 1); } private TreeNode BuildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) { //Base case - reached the end of the traversals if(inStart > inEnd || postStart > postEnd) { return null; } //Create the root node with the last element in the postorder traversal TreeNode root = new TreeNode(postorder[postEnd]); //Find the index of the root node in the inorder traversal int rootIndex = Array.IndexOf(inorder, root.val); //Use the index to calculate the number of nodes in the left and right subtrees int leftTreeSize = rootIndex - inStart; int rightTreeSize = inEnd - rootIndex; //Recursively build the left and right subtrees root.left = BuildTreeHelper(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftTreeSize - 1); root.right = BuildTreeHelper(inorder, postorder, rootIndex + 1, inEnd, postStart + leftTreeSize, postEnd - 1); return root; } }