Construct Binary Tree from Inorder and Postorder Traversal

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

Example:

Input:  postorder={9,15,7,20,3} , 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 ConstructBinaryTreeFromIPT {
    public static void main(String[] args) {
        int postorder[] = { 3, 15, 7, 20, 3 };
        int inorder[] = { 9, 3, 15, 20, 7 };
        TreeNode root = buildTree(inorder, postorder);
        printTree(root);
    }

    static TreeNode buildTree(int[] inorder, int instart, int inend,
             int[] postorder, int poststart, int postend) {
        if (poststart > postend)
            return null;
        TreeNode root = new TreeNode(postorder[postend]);
        int k = 0;
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == postorder[postend]) {
                k = i;
                break;
            }
        }
        root.left = buildTree(inorder, instart, k - 1, postorder,
                     poststart, poststart + k - 1 - instart);
        root.right = buildTree(inorder, k + 1, inend, postorder,
                         postend - inend + k, postend - 1);
        return root;
    }

    static TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0,
                     postorder.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;
        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;
    }
};


TreeNode *buildTree(vector<int> &inorder,int instart,int inend,
        vector<int> &postorder,int poststart,int postend)
{
        if(poststart>postend)
              return NULL;
        TreeNode *root=new TreeNode(postorder[postend]);
        int k=0;
        for(int i=instart;i<=inend;i++)
        {
            if(inorder[i]==postorder[postend])
            {
                k=i;
                break;
            }
        }
        root->left=buildTree(inorder,instart,k-1,postorder,
                      poststart,poststart+k-1-instart);
        root->right=buildTree(inorder,k+1,inend,postorder,
                     postend-inend+k,postend-1);
        return root;
    }
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
 {
    return buildTree(inorder,0,inorder.size()-1,postorder,0,postorder.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> postorder ={9,15,7,20,3};
  vector<int> inorder = {9,3,15,20,7};
  TreeNode *root=buildTree(inorder,postorder);
  printTree(root);
  return 0;
}