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.

1. First, check if the list is empty.
2. Define the root of the tree as the first element in the preorder list.
3. Find the position of the root value in the inorder list, which will help in dividing the inorder list into left and right subtrees.
4. Calculate the length of the left subtree using the position of the root value in the inorder list.
5. Construct the left subtree by recursively calling the constructTree() function with the preorder and inorder lists corresponding to the left subtree.
6. Construct the right subtree by recursively calling the constructTree() function with the preorder and inorder lists corresponding to the right subtree.
7. 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
        HashMap map = 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;
    }
}