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)