Construct Binary Tree from Preorder and Inorder Traversal

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

Example:

Input:  preorder={3,9,20,15,7},inorder={9,3,15,20,7}
Output: tree={3,9,20,null,null,15,7}

Approach

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class ConstructBinaryTreeFromPIT {
    public static void main(String[] args) {
        int preorder[] = { 3, 9, 20, 15, 7 };
        int inorder[] = { 9, 3, 15, 20, 7 };
        TreeNode root = buildTree(preorder, inorder);
        printTree(root);
    }

    static int prestart = 0;

    static TreeNode buildTree(int[] preorder, int[] inorder,
                 int instart, int inend) {
        if (instart > inend)
            return null;
        TreeNode root = new TreeNode(preorder[prestart++]);
        if (instart == inend)
            return root;
        int k = 0;
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == root.val) {
                k = i;
                break;
            }
        }

        root.left = buildTree(preorder, inorder, instart, k - 1);
        root.right = buildTree(preorder, inorder, k + 1, inend);
        return root;
    }

    static TreeNode buildTree(int[] preorder, int[] inorder) {
        prestart = 0;
        if (preorder.length == 0)
            return null;
        return buildTree(preorder, inorder, 0, inorder.length - 1);
    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            root = q.poll();
            if (root == null)
                vec.add("null");
            else
                vec.add(String.valueOf(root.val));
            if (root != null) {
                q.add(root.left);
                q.add(root.right);
            }
        }
        int j = vec.size() - 1;
        while (j > 0 && vec.get(j) == "null")
            j--;
        for (int i = 0; i < j; i++)
            System.out.print(vec.get(i) + ",");
        System.out.print(vec.get(j));
    }
}

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;
    }
}

  

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};

int prestart;
TreeNode *buildTree(vector<int> &preorder,vector<int> &inorder,
      int instart,int inend)
{
        if(instart>inend)
              return NULL;
        TreeNode *root=new TreeNode(preorder[prestart++]);
        if(instart==inend)
              return root;
        int k=0;
        for(int i=instart;i<=inend;i++)
        {
            if(inorder[i]==root->data)
            {
                k=i;
                break;
            }
        }
        
        root->left=buildTree(preorder,inorder,instart,k-1);
        root->right=buildTree(preorder,inorder,k+1,inend);
        return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
{
        prestart=0;
        if(preorder.size()==0)
              return NULL;
        return buildTree(preorder,inorder,0,inorder.size()-1);
}

void printTree(TreeNode *root)
{
    queue<TreeNode*>q;
    q.push(root);
    vector<string> vec;
    while(!q.empty())
     {
         root=q.front();
         q.pop();
         if(root==NULL)
            vec.push_back("null");
         else
            vec.push_back(to_string(root->data));
        if(root!=NULL)
          {
              q.push(root->left);
              q.push(root->right);
          }
     }
     int j=vec.size()-1;
     while(j>0&&vec[j]=="null")
        j--;
      vec.resize(j);
      for(int i=0;i<j;i++)
        cout<<vec[i]<<",";
      cout<<vec[j];
}
int main()
{
  vector<int> preorder ={3,9,20,15,7};
  vector<int> inorder = {9,3,15,20,7};
  TreeNode *root=buildTree(preorder,inorder);
  printTree(root);
  return 0;
}