Blogs Hub

by Sumit Chourasia | Nov 17, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Construct Binary Tree from Preorder and Inorder Traversal - Array - Medium - LeetCode

Construct Binary Tree from Preorder and Inorder Traversal - Array - Medium - LeetCode

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

 

/**
 * 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) {
        return Helper(0, 0, inorder.Length -1, preorder, inorder);
    }
    
    public TreeNode Helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder){
        if(preStart > preorder.Length-1 || inStart > inEnd){
            return null;
        }
        
        var root = new TreeNode(preorder[preStart]);
        
        int i=0;
        for(i= inStart; i< inEnd; i++ ){
            if(inorder[i]==root.val){
                break;   
            }
        }
        
        root.left = Helper(preStart+1, inStart, i-1, preorder, inorder);
        root.right = Helper(preStart + i - inStart +1, i+1, inEnd, preorder, inorder);
        
        return root;
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

Contributed By: Sumit Chourasia
Delete Duplicate Emails - SQL - Easy - LeetCode
Contributed By: Sumit Chourasia
Two Strings - HashMap - Easy - HackerRank
Contributed By: Sumit Chourasia
Richest Customer Wealth - String - Easy - LeetCode
Contributed By: Sumit Chourasia
Reformat Phone Number - String - Easy - LeetCode