Binary Tree from Preorder and Inorder String Leetcode

Problem: Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

 Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

 Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

This problem is popular in LeetCode and GeeksForGeeks A collection of hundreds of interview questions and solutions are available in our blog at Interview Question

Solution:

	/**
	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
	*/
	import java.util.*;
	class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { val = x; }
	}
	public class BinaryTreeFromPreInorder{
	static Map<Integer, Integer> inmap=new HashMap<>();
	/**
	Method1:
	-recursively build the tree using the inorder and preorder strings
	Ref:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34538/My-Accepted-Java-Solution
	*/
	public static TreeNode buildTree(int[] iarr, int[] prearr){
	for(int i=0;i<iarr.length; i++){
	inmap.put(iarr[i], i);
	}
	return helper(iarr, prearr, 0, iarr.length-1, 0);
	}
	public static TreeNode helper(int[] iarr, int[] prearr, int istart, int iend, int pstart){
	//exit conditions
	if(pstart>prearr.length-1 || istart>iend){
	return null;
	}
	//get the root node from the pre-order array
	TreeNode root = new TreeNode(prearr[pstart]);
	//get the left subtree whose portion will be from istart to index of root in the preorder string
	int inindex = inmap.get(root.val);
	System.out.println("root is:"+root.val);
	root.left = helper(iarr, prearr, istart, inindex-1, pstart+1);//inindex holds the root node so the left portion is used
	//get the right node
	root.right = helper(iarr, prearr, inindex+1, iend, pstart+ inindex -istart+1);//inindex holds the root node so the right portion is used
	return root;
	}
	public static void main(String[] args){
	int[] preorder = new int[] {3,9,20,15,7};
	int [] inorder = new int[]{9,3,15,20,7};
	TreeNode root = buildTree(inorder, preorder);
	System.out.println("tree root is:"+root.val);
	}
	}

view raw BinaryTreeFromPreorderAndInorder.java hosted with ❤ by GitHub