Solution For Construct Binary Tree From Preorder And Inorder Traversal
Problem Statement:
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Example:
Input:
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Output:
3
/ \
9 20
/ \
15 7
Solution:
The strategy here is to use the first element of the preorder list to construct the root of the binary tree. Then, we use the root value to divide the inorder list into left and right subtrees. We then recursively construct the left and right subtrees using the remaining elements in the preorder list.
Steps:
1. Define the recursive function constructTree(preorder, inorder, in_start, in_end) that returns a constructed binary tree in that subtree in inorder from in_start to in_end.
- First, check if the list is empty.
- Define the root of the tree as the first element in the preorder list.
- Find the position of the root value in the inorder list, which will help in dividing the inorder list into left and right subtrees.
- Calculate the length of the left subtree using the position of the root value in the inorder list.
- Construct the left subtree by recursively calling the constructTree() function with the preorder and inorder lists corresponding to the left subtree.
- Construct the right subtree by recursively calling the constructTree() function with the preorder and inorder lists corresponding to the right subtree.
- Return the root of the constructed binary tree.
Code:
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def constructTree(preorder, inorder, in_start, in_end):
if in_start > in_end:
return None
root_val = preorder.pop(0)
root = TreeNode(root_val)
root_index_inorder = inorder.index(root_val)
length_left_subtree = root_index_inorder - in_start
root.left = constructTree(preorder, inorder, in_start, root_index_inorder - 1)
root.right = constructTree(preorder, inorder, root_index_inorder + 1, in_end)
return root
return constructTree(preorder, inorder, 0, len(inorder)-1)
Time Complexity: O(n^2)
In the worst case, the function runs O(n) times, and each time it searches for the root value in the inorder list which takes O(n).
Space Complexity: O(n)
In the worst case, the function uses O(n) space to store the binary tree.
Step by Step Implementation For Construct Binary Tree From Preorder And Inorder 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[] preorder, int[] inorder) { //check for empty input if(preorder.length == 0 || inorder.length == 0){ return null; } //initialize a hashmap for inorder traversal HashMapmap = new HashMap (); for(int i = 0; i < inorder.length; i++){ map.put(inorder[i], i); } //call helper function return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map); } public TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, HashMap map){ //base case if(preStart > preEnd || inStart > inEnd){ return null; } //create the root node with the first element in the preorder traversal TreeNode root = new TreeNode(preorder[preStart]); //find the index of the root node in the inorder traversal int inRoot = map.get(root.val); //calculate the number of nodes in the left subtree int numsLeft = inRoot - inStart; //recursively build the left and right subtrees root.left = helper(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, map); root.right = helper(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, map); return root; } }
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: # if the list is empty, return None if not preorder: return None # create a new TreeNode with the first element from preorder root = TreeNode(preorder[0]) # find the index of the root in inorder index = inorder.index(root.val) # create the left and right subtrees root.left = self.buildTree(preorder[1:index+1], inorder[:index]) root.right = self.buildTree(preorder[index+1:], inorder[index+1:]) return root
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {number[]} preorder * @param {number[]} inorder * @return {TreeNode} */ var buildTree = function(preorder, inorder) { // base case if (!preorder.length) return null; // recursive case let root = new TreeNode(preorder[0]); let rootIndex = inorder.indexOf(preorder[0]); root.left = buildTree(preorder.slice(1, rootIndex + 1), inorder.slice(0, rootIndex)); root.right = buildTree(preorder.slice(rootIndex + 1), inorder.slice(rootIndex + 1)); 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& preorder, vector & inorder) { // Base case if (preorder.size() == 0 || inorder.size() == 0) return nullptr; // The first element in preorder is always the root TreeNode* root = new TreeNode(preorder[0]); // Find the index of the root in inorder int rootIdx; for (int i = 0; i < inorder.size(); i++) { if (inorder[i] == root->val) { rootIdx = i; break; } } // Recursively build the left and right subtrees vector leftInorder(inorder.begin(), inorder.begin() + rootIdx); vector rightInorder(inorder.begin() + rootIdx + 1, inorder.end()); vector leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + rootIdx); vector rightPreorder(preorder.begin() + 1 + rootIdx, preorder.end()); root->left = buildTree(leftPreorder, leftInorder); root->right = buildTree(rightPreorder, rightInorder); return root; } };
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public TreeNode BuildTree(int[] preorder, int[] inorder) { // base case if (preorder.Length == 0 || inorder.Length == 0) { return null; } // create a hashmap of the inorder array elements for quick lookup var inorderMap = new Dictionary(); for (int i = 0; i < inorder.Length; i++) { inorderMap.Add(inorder[i], i); } // create the root node from the first element in the preorder array TreeNode root = new TreeNode(preorder[0]); // create a stack to keep track of nodes as we build the tree Stack stack = new Stack (); stack.Push(root); // create pointers for the preorder and inorder arrays int preorderPointer = 1; int inorderPointer = 0; // iterate over the rest of the preorder array while (preorderPointer < preorder.Length) { // create a node from the next preorder array element TreeNode node = new TreeNode(preorder[preorderPointer]); // if the node's value is in the inorder array to the left of the current inorder pointer // it is the left child of the node at the top of the stack if (inorderMap[node.val] < inorderMap[stack.Peek().val]) { stack.Peek().left = node; } // if the node's value is in the inorder array to the right of the current inorder pointer // it is the right child of the node at the top of the stack else { // keep popping nodes off the stack until we find a node whose value is to the left of the current node's value // in the inorder array // when we find that node, the current node is its right child TreeNode parent = null; while (stack.Count > 0 && inorderMap[node.val] > inorderMap[stack.Peek().val]) { parent = stack.Pop(); } parent.right = node; } // push the current node onto the stack stack.Push(node); // increment the preorder and inorder pointers preorderPointer++; inorderPointer++; } return root; } }