package com.interview.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Date 11/07/2015
 * @author Tushar Roy
 *
 * Given an inorder traversal construct all binary search trees possible.
 * Total number of binary search tree possible is Catalan number.
 */
public class ConstructAllBinaryTreeFromInorderTraversal {

    public List<Node> construct(int inorder[]) {
        return construct(inorder, 0, inorder.length - 1);
    }

    private List<Node> construct(int inorder[], int start, int end) {
        if (start > end) {
            return Collections.singletonList(null);
        }
        List<Node> allTrees = new ArrayList<>();
        for (int root = start; root <= end; root++) {
            //get all subtrees from left and right side.
            List<Node> allLeftSubstrees = construct(inorder, start, root - 1);
            List<Node> allRightSubstrees = construct(inorder, root + 1, end);
            //iterate through them in all combination and them connect them to root
            //and add to allTrees.
            for (Node left : allLeftSubstrees) {
                for (Node right : allRightSubstrees) {
                    Node node = Node.newNode(inorder[root]);
                    node.left = left;
                    node.right = right;
                    allTrees.add(node);
                }
            }
        }
        return allTrees;
    }

    public void printAllTrees(List<Node> allTrees) {
        TreeTraversals tt = new TreeTraversals();
        System.out.println("Total number of trees " + allTrees.size());
        for(Node node : allTrees) {
            tt.inOrder(node);
            System.out.println();
            tt.preOrder(node);
            System.out.print("\n\n");
        }
    }

    public static void main(String args[]) {
        int inorder[] = {1, 2, 3, 4, 5};
        ConstructAllBinaryTreeFromInorderTraversal ct = new ConstructAllBinaryTreeFromInorderTraversal();
        List<Node> allTrees = ct.construct(inorder);
        ct.printAllTrees(allTrees);
    }
}

@@ -165,43 +165,51 @@
 ven 
-an inorder traversal con
+n, generate all 
 struct
- all 
+urally unique BST's (
 bina
@@ -223,25 +223,41 @@
 ch trees
- possible
+) that store values 1...n
 .%0A * Tot
@@ -316,16 +316,83 @@
 number.%0A
+ *%0A * https://leetcode.com/problems/unique-binary-search-trees-ii/%0A
  */%0Apubl
@@ -472,90 +472,136 @@
 de%3E 
-construct(int inorder%5B%5D) %7B%0A        return construct(inorder, 0, inorder.length - 1
+generateTrees(int n) %7B%0A        if (n == 0) %7B%0A            return Collections.emptyList();%0A        %7D%0A        return construct(1, n
 );%0A 
@@ -647,23 +647,8 @@
 int 
-inorder%5B%5D, int 
 star
@@ -962,25 +962,16 @@
 nstruct(
-inorder, 
 start, r
@@ -1037,17 +1037,8 @@
 uct(
-inorder, 
 root
@@ -1321,21 +1321,12 @@
 ode(
-inorder%5B
 root
-%5D
 );%0A 
@@ -1926,49 +1926,8 @@
 ) %7B%0A
-        int inorder%5B%5D = %7B1, 2, 3, 4, 5%7D;%0A
     
@@ -2065,25 +2065,23 @@
  ct.
-construct(inorder
+generateTrees(3
 );%0A 

update tree generation solution