Find all possible binary trees with given Inorder Traversal

Last Updated : 25 Dec, 2022

Given an array that represents Inorder Traversal, find all possible Binary Trees with the given Inorder traversal and print their preorder traversals.
Examples:

Input:   in[] = {3, 2};
Output:  Preorder traversals of different possible Binary Trees are:
         3 2
         2 3
Below are different possible binary trees
    3        2
     \      /
      2    3

Input:   in[] = {4, 5, 7};
Output:  Preorder traversals of different possible Binary Trees are:
          4 5 7 
          4 7 5 
          5 4 7 
          7 4 5 
          7 5 4 
Below are different possible binary trees
  4         4           5         7       7
   \          \       /   \      /       /
    5          7     4     7    4       5
     \        /                  \     /
      7      5                    5   4

We strongly recommend you to minimize your browser and try this yourself first.
Let given inorder traversal be in[]. In the given traversal, all nodes in left subtree of in[i] must appear before it and in right subtree must appear after it. So when we consider in[i] as root, all elements from in[0] to in[i-1] will be in left subtree and in[i+1] to n-1 will be in right subtree. If in[0] to in[i-1] can form x different trees and in[i+1] to in[n-1] can from y different trees then we will have x*y total trees when in[i] as root. So we simply iterate from 0 to n-1 for root. For every node in[i], recursively find different left and right subtrees. If we take a closer look, we can notice that the count is basically n’th Catalan number. We have discussed different approaches to find n’th Catalan number here.
The idea is to maintain a list of roots of all Binary Trees. Recursively construct all possible left and right subtrees. Create a tree for every pair of left and right subtree and add the tree to list. Below is detailed algorithm.

1) Initialize list of Binary Trees as empty.  
2) For every element in[i] where i varies from 0 to n-1,
    do following
......a)  Create a new node with key as 'arr[i]', 
          let this node be 'node'
......b)  Recursively construct list of all left subtrees.
......c)  Recursively construct list of all right subtrees.
3) Iterate for all left subtrees
   a) For current leftsubtree, iterate for all right subtrees
        Add current left and right subtrees to 'node' and add
        'node' to list.

C++

// C++ program to find binary tree with given inorder
// traversal
#include <bits/stdc++.h>
using namespace std;
 
// Node structure
struct Node
{
    int key;
    struct Node *left, *right;
};
 
// A utility function to create a new tree Node
struct Node *newNode(int item)
{
    struct Node *temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
// A utility function to do preorder traversal of BST
void preorder(Node *root)
{
    if (root != NULL)
    {
        printf("%d ", root->key);
        preorder(root->left);
        preorder(root->right);
    }
}
 
// Function for constructing all possible trees with
// given inorder traversal stored in an array from
// arr[start] to arr[end]. This function returns a
// vector of trees.
vector<Node *> getTrees(int arr[], int start, int end)
{
    // List to store all possible trees
    vector<Node *> trees;
 
    /* if start > end then subtree will be empty so
    returning NULL in the list */
    if (start > end)
    {
        trees.push_back(NULL);
        return trees;
    }
 
    /* Iterating through all values from start to end
        for constructing left and right subtree
        recursively */
    for (int i = start; i <= end; i++)
    {
        /* Constructing left subtree */
        vector<Node *> ltrees = getTrees(arr, start, i-1);
 
        /* Constructing right subtree */
        vector<Node *> rtrees = getTrees(arr, i+1, end);
 
        /* Now looping through all left and right subtrees
        and connecting them to ith root below */
        for (int j = 0; j < ltrees.size(); j++)
        {
            for (int k = 0; k < rtrees.size(); k++)
            {
                // Making arr[i] as root
                Node * node = newNode(arr[i]);
 
                // Connecting left subtree
                node->left = ltrees[j];
 
                // Connecting right subtree
                node->right = rtrees[k];
 
                // Adding this tree to list
                trees.push_back(node);
            }
        }
    }
    return trees;
}
 
// Driver Program to test above functions
int main()
{
    int in[] = {4, 5, 7};
    int n = sizeof(in) / sizeof(in[0]);
 
    vector<Node *> trees = getTrees(in, 0, n-1);
 
    cout << "Preorder traversals of different "
         << "possible Binary Trees are \n";
    for (int i = 0; i < trees.size(); i++)
    {
        preorder(trees[i]);
        printf("\n");
    }
    return 0;
}

Java

// Java program to find binary tree with given inorder
// traversal
import java.util.Vector;
 
/* Class containing left and right child of current 
 node and key value*/
class Node {
    int data;
    Node left, right;
 
    public Node(int item) {
        data = item;
        left = null;
        right = null;
    }
}
 
/* Class to print Level Order Traversal */
class BinaryTree {
 
    Node root;
 
    // A utility function to do preorder traversal of BST
    void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data + " "    );
            preOrder(node.left);
            preOrder(node.right);
        }
    }
 
    // Function for constructing all possible trees with
    // given inorder traversal stored in an array from
    // arr[start] to arr[end]. This function returns a
    // vector of trees.
    Vector<Node> getTrees(int arr[], int start, int end) {
 
        // List to store all possible trees
        Vector<Node> trees= new Vector<Node>();
 
        /* if start > end then subtree will be empty so
         returning NULL in the list */
        if (start > end) {
            trees.add(null);
            return trees;
        }
 
        /* Iterating through all values from start to end
         for constructing left and right subtree
         recursively */
        for (int i = start; i <= end; i++) {
            /* Constructing left subtree */
            Vector<Node> ltrees = getTrees(arr, start, i - 1);
             
            /* Constructing right subtree */
            Vector<Node> rtrees = getTrees(arr, i + 1, end);
 
            /* Now looping through all left and right subtrees
             and connecting them to ith root below */
            for (int j = 0; j < ltrees.size(); j++) {
                for (int k = 0; k < rtrees.size(); k++) {
 
                    // Making arr[i] as root
                    Node node = new Node(arr[i]);
 
                    // Connecting left subtree
                    node.left = ltrees.get(j);
 
                    // Connecting right subtree
                    node.right = rtrees.get(k);
 
                    // Adding this tree to list
                    trees.add(node);
                }
            }
        }
        return trees;
    }
 
    public static void main(String args[]) {
        int in[] = {4, 5, 7};
        int n = in.length;
        BinaryTree tree = new BinaryTree();
        Vector<Node> trees = tree.getTrees(in, 0, n - 1);
        System.out.println("Preorder traversal of different "+
                           " binary trees are:");
        for (int i = 0; i < trees.size(); i++) {
            tree.preOrder(trees.get(i));
            System.out.println("");
        }
    }
}

Python3

# Python program to find binary tree with given 
# inorder traversal
 
# Node Structure
class Node:
 
    # Utility to create a new node
    def __init__(self , item):
        self.key = item
        self.left = None
        self.right = None
 
# A utility function to do preorder traversal of BST
def preorder(root):
    if root is not None:
        print (root.key,end=" ")
        preorder(root.left)
        preorder(root.right)
 
 
# Function for constructing all possible trees with
# given inorder traversal stored in an array from
# arr[start] to arr[end]. This function returns a
# vector of trees.
def getTrees(arr , start , end):
 
    # List to store all possible trees
    trees = [] 
     
    """ if start > end then subtree will be empty so
    returning NULL in the list """
    if start > end :
        trees.append(None)
        return trees
     
 
    """ Iterating through all values from start to end
        for constructing left and right subtree
        recursively """
    for i in range(start , end+1):
 
        # Constructing left subtree
        ltrees = getTrees(arr , start , i-1)
         
        # Constructing right subtree
        rtrees = getTrees(arr , i+1 , end)
         
        """ Looping through all left and right subtrees 
        and connecting to ith root below"""
        for j in ltrees :
            for k in rtrees :
 
                # Making arr[i]  as root
                node  = Node(arr[i])
     
                # Connecting left subtree
                node.left = j  
 
                # Connecting right subtree
                node.right = k 
 
                # Adding this tree to list
                trees.append(node)
    return trees
 
# Driver program to test above function
inp = [4 , 5, 7]
n = len(inp)
 
trees = getTrees(inp , 0 , n-1)
 
print ("Preorder traversals of different possible\
 Binary Trees are ")
for i in trees :
    preorder(i);
    print ("")
 
# This program is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to find binary tree 
// with given inorder traversal 
using System;
using System.Collections.Generic;
 
/* Class containing left and right
   child of current node and key value*/
public class Node
{
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = null;
        right = null;
    }
}
 
/* Class to print Level Order Traversal */
class GFG
{
public Node root;
 
// A utility function to do
// preorder traversal of BST 
public virtual void preOrder(Node node)
{
    if (node != null)
    {
        Console.Write(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}
 
// Function for constructing all possible
// trees with given inorder traversal 
// stored in an array from arr[start] to 
// arr[end]. This function returns a 
// vector of trees. 
public virtual List<Node> getTrees(int[] arr, 
                                   int start, 
                                   int end)
{
 
    // List to store all possible trees 
    List<Node> trees = new List<Node>();
 
    /* if start > end then subtree will be 
    empty so returning NULL in the list */
    if (start > end)
    {
        trees.Add(null);
        return trees;
    }
 
    /* Iterating through all values from 
    start to end for constructing left 
    and right subtree recursively */
    for (int i = start; i <= end; i++)
    {
        /* Constructing left subtree */
        List<Node> ltrees = getTrees(arr, start, i - 1);
 
        /* Constructing right subtree */
        List<Node> rtrees = getTrees(arr, i + 1, end);
 
        /* Now looping through all left and 
        right subtrees and connecting them 
        to ith root below */
        for (int j = 0; j < ltrees.Count; j++)
        {
            for (int k = 0; k < rtrees.Count; k++)
            {
 
                // Making arr[i] as root 
                Node node = new Node(arr[i]);
 
                // Connecting left subtree 
                node.left = ltrees[j];
 
                // Connecting right subtree 
                node.right = rtrees[k];
 
                // Adding this tree to list 
                trees.Add(node);
            }
        }
    }
    return trees;
}
 
// Driver Code
public static void Main(string[] args)
{
    int[] arr = new int[] {4, 5, 7};
    int n = arr.Length;
    GFG tree = new GFG();
    List<Node> trees = tree.getTrees(arr, 0, n - 1);
    Console.WriteLine("Preorder traversal of different " + 
                                    " binary trees are:");
    for (int i = 0; i < trees.Count; i++)
    {
        tree.preOrder(trees[i]);
        Console.WriteLine("");
    }
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
  
// Javascript program to find binary tree 
// with given inorder traversal 
 
/* Class containing left and right
   child of current node and key value*/
class Node
{
    constructor(item)
    {
        this.data = item;
        this.left = null;
        this.right = null;
    }
}
 
/* Class to print Level Order Traversal */
 
var root = null;
 
// A utility function to do
// preorder traversal of BST 
function preOrder(node)
{
    if (node != null)
    {
        document.write(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}
 
// Function for constructing all possible
// trees with given inorder traversal 
// stored in an array from arr[start] to 
// arr[end]. This function returns a 
// vector of trees. 
function getTrees(arr, start, end)
{
 
    // List to store all possible trees 
    var trees = [];
 
    /* if start > end then subtree will be 
    empty so returning NULL in the list */
    if (start > end)
    {
        trees.push(null);
        return trees;
    }
 
    /* Iterating through all values from 
    start to end for constructing left 
    and right subtree recursively */
    for (var i = start; i <= end; i++)
    {
        /* Constructing left subtree */
        var ltrees = getTrees(arr, start, i - 1);
 
        /* Constructing right subtree */
        var rtrees = getTrees(arr, i + 1, end);
 
        /* Now looping through all left and 
        right subtrees and connecting them 
        to ith root below */
        for (var j = 0; j < ltrees.length; j++)
        {
            for (var k = 0; k < rtrees.length; k++)
            {
 
                // Making arr[i] as root 
                var node = new Node(arr[i]);
 
                // Connecting left subtree 
                node.left = ltrees[j];
 
                // Connecting right subtree 
                node.right = rtrees[k];
 
                // Adding this tree to list 
                trees.push(node);
            }
        }
    }
    return trees;
}
 
// Driver Code
var arr = [4, 5, 7];
var n = arr.length;
var trees = getTrees(arr, 0, n - 1);
document.write("Preorder traversal of different " + 
                                " binary trees are:<br>");
for(var i = 0; i < trees.length; i++)
{
    preOrder(trees[i]);
    document.write("<br>");
}
 
// This code is contributed by rrrtnx.
 
</script>

Output:

Preorder traversals of different possible Binary Trees are 
4 5 7 
4 7 5 
5 4 7 
7 4 5 
7 5 4

Time Complexity: O(n^3).
The time complexity of the above algorithm is O(n^3). The getTrees() function is called for every element of the array. Inside the function, two for loops are used for constructing left and right subtrees for every element of the array.

Space Complexity: O(n^2).
The space complexity of the above algorithm is O(n^2). The getTrees() function is called for every element of the array. Inside the function, two for loops are used for constructing left and right subtrees for every element of the array. Vector of size n is used for storing the list of trees.

Thanks to Utkarsh for suggesting above solution.
This problem is similar to the problem discussed here.