## Google Interview Question

- 1of 3 votes
Given an inorder traversal only for a binary tree (not necessarily a

BST), give a pseudo code to generate all possible binary trees for

this traversal sequence.

Firstly, how many binary trees can be generated given an in-order

traversal? I know that given 'n' nodes, number of BTs possible is

(2^n)-n. But if we are given a specific in-order sequence, can we cut

down on this number?

**Country:**United States

Good method. But it's hard for me to implement it in this way. It will be very appreciate if you can provide the code.

the # of trees with same traversal should then equal

catalan numbers ? ie. C(2n,n)/(n+1) with n being the number of nodes

host is providing a good method. please understand people are learning from all different level, you were there too.

int NumOfBST(string inorder){

int number = sizeof(inorder);

TreeNum(number);

}

int TreeNum(int n){

if(n == 0 || n == 1){

return 1;

}

int sum = 0;

int num = n;

while(num>0){

sum += TreeNum(num-1)*TreeNum(n-num);

num--;

}

return sum

}

Looks about right for getting the number of trees (though you should memoize returned values of TreeNum to avoid exponential runtime).

@eugene.yarovoi - the formula Trees(n) which you gave has a very small mistake right? Trees(N-2)*Trees(2) should be Trees(N-2)*Trees(1) because one node will be the root separating the left sub-tree and the right sub-tree.

Here's some code which hopefully is implementing his idea properly. The initial call should pass 0 for argument "start" and order.length for argument "to".

```
ArrayList<Node> trees(int[] order, int start, int to) {
ArrayList<Node> trees = new ArrayList<Node>();
if(start > to) {
trees.add(null);
return trees;
}
int len = order.length;
for(int i=start; i<=to; i++) {
ArrayList<Node> leftTrees = trees(order, start, i-1);
ArrayList<Node> rightTrees = trees(order, i+1, to);
for(Node left : leftTrees) {
for(Node right : rightTrees) {
Node parent = new Node(order[i]);
parent.left = left;
parent.right = right;
trees.add(parent);
}
}
}
return trees;
}
```

Grrr sorry I meant to say pass order.length - 1 for argument "to". Basically the method returns all BST for the given order array using arguments from [start, to] inclusive.

As per the question number of BT will be less than 2^n -n.

But if i use your logic it gives me more than that. Take an example n=5 ,2^n -n would give us 32-5=27 but your logic returns 42. Could you let me clarify on this difference.

I think visu's concern is from the following description in the original question:

`I know that given 'n' nodes, number of BTs possible is (2^n)-n`

However, I think this description is non-sense and wrong!

@Alva0930: I see. I don't know where the person who posted the problem statement is getting that formula. Maybe they just got it wrong, or maybe they interpreted the question differently.

```
public static int NumTreesOfAGivenInorderTraversal(int[] arr, int start, int end)
{
if (arr.Length == 0 || end < start)
return 1;
if (start == end)
{
return 1;
}
int numTrees = 0;
for (int i = start; i <= end; i++)
{
int left = NumTreesOfAGivenInorderTraversal(arr, start, i - 1);
int right = NumTreesOfAGivenInorderTraversal(arr, i+1, end);
numTrees += (left * right);
}
return numTrees;
}
static void Main(string[] args)
{
Console.WriteLine(NumTreesOfAGivenInorderTraversal(new int[]{1, 2, 3, 4}, 0, 3));
Console.ReadKey();//press any key to exit.
}
```

Dear All,

I don't expected to see Dynamic Programming problem in the interview but will not surprise if google does. By the way, as Eugene said, let's the function Cnt(i...j) is the counting function defined on node sequence Node[i],...,Node[j]. Each single node can be root of the tree which reduce the problem into Left:Cnt(i,..,k-1) and Right:Cnt(k+1,...,j) so the Recursion is given as follow:

```
Cnt(i...j) = Sum_{i<=k<=j} Cnt(i,..,k-1) * Cnt(k,..,k) * Cnt(k+1,..,j) where
Cnt(i..j) = 1 if j == i or j < i (two base cases)
```

Then we will need a Matrix of NxN and start filling the matrix from i=0 to n and j begins from j=i. This will give an interesting pyramid of number which I need you guy to help me derive the equation.

```
Total
N = 1 1 1
N = 2 1 1 2
N = 3 2 1 2 5
N = 4 5 2 2 5 14
N = 5 14 5 4 5 14 42
N = 6 42 14 10 10 14 42 122
```

I only post this because the number looks familiar but I can figure it out. Some math help would be very appreciate.

I've definitely been asked dynamic programming questions in interviews. Not that uncommon.

May I ask what is the inorder traversal is? If like the normal definition, it is leftchild->self->rightchild.

Then in the sequence with length n, we call Partition(sequence) which iteratively pick each one to be the root. All the values on left make the left subtree and others on right make the right subtree. So you can call the Partition(subsequence) recursively.

But if you want to know the number of possible trees, I think inductive method could help. If there are N(k) trees correspond to a sequence with length k, then what is N(k+1) by adding the new value or node to the tail of the sequence? I think the answer is 2*N(k). Because you can treat the new node as the last right child or the parent with the previous tree(all possible trees corresponding to sequence k) as its left-child. By knowing N(1) is 1, you have 2^(n-1) for sequence k. Where is the 2^n-n from?

sorry, the 2nd last sentence should be "By knowing N(1) is 1, you have 2^(n-1) for sequence n. "

I can understand a bit of what you mentioned about the tree construction but I don't agree to 2^(n-1). Given a sequence say - "123" which represents the in-order traversal of a BT (not necessarily a BST), the number of binary trees possible are only 3 (which is equal to the length of the string - n)

Possible trees:

```
1 2 3
\ / \ /
2 1 3 2
\ /
3 1
```

The best way I can find to output all the possible trees is also follow this inductive rule.

//global variable containing the roots of all the trees

List<Node> treeList=new LinkedList<Node>()

//augment all the trees in the treeList by newNode

void augmentTree(Node newNode){

//add newNode to the current trees

for(Node root: treeList){

root.Max().rightChild=newNode;

}

//add current trees to the newNode as left subtrees and append the newNode to the treeList

int l=treeList.length();

for(int i=0;i<l;i++){

newNode.leftChild=treeList.get(i)

treeList.add(newNode);

}

}

void main(){

int[] sequence=readInput();//suppose sequence is an array of integer

Node newNode=new Node(sequence[0]);//put the first Node in

treeList.add(newNode);

//from the 2nd value in sequence, augument the trees one by one

//results are stored and modified in treeList

for(int i=1; i<sequence.length();i++){

newNode=new Node(sequence[i]);

augumentTree(newNode);

}

//all the trees are stored in treeList now

}

@someone, thx!

Now we have 3 possible situations for adding k+1 to k...although without right subtree, there are two situations are the same.

So I should add one more block in augmentTree(Node n), if root has right child, then n.leftchild=root.rightchild and root.rightchild=n

Does anyone know how to solve this problem if the in-order traversal is postorder or pre-order traversal? left-right-self/right-left-self.

I think there are 5 cases in 3, not 4 cases.

2

/ \

1 3

1

\

2

\

3

1

\

3

/

2

3

/

1

\

2

3

/

2

/

1

Dynamic programming:

Tree (n) is some sort of data structure which stores all possible trees with n nodes given the inorder traversal: 1 2 3 4 5

We are going through the sequence from right to left, so 5 comes first then 4 and so on.

We start by computing Tree (0) which is 0

Tree (1) = 5

Tree (2) =

4 and 5

\ /

5 4

Tree (3) =

We join node 3 with Tree (2) in two ways:

3 and Tree (2)

\ /

Tree(2) 3

This results in 4 trees in total, which are:

3 and 3 and 4 and 5

\ \ / \ /

4 5 3 5 4

\ / /

5 4 3

Similarly, compute Tree (4), Tree (5)....

Problem solved.

If we just need count the number, how about this?

void testMain()

{

vector<char> inorder;

... //init inorder.

int total = CountNumberFromInOrder(inorder,0,inorder.size());

}

int CountNumberFromInOrder(vector<T> &inorder, int start, int end)

{

if (inorder.size() == 0) return 0;

if (start == end) return 1;

int sum = 0;

for (int i=start; i<end;i++){

int left = CountNumberFromInOrder(inorder, start, i);

int right = CountNumberFromInOrder(inorder, i+1, end);

int sum += left*right;

}

```
#include<stdio.h>
int find_no(int n)
{
if(n<=1)
return 1;
else
{
int sum=0;
for(int i=1;i<=n;i++)
{
sum=sum+(find_no(i-1)*find_no(n-i));
}
return sum;
}
}
int main()
{
int n;
scanf("%d",&n);
int res=find_no(n);
printf("%d\n",res);
return 0;
}
```

Refer to comment of eugene.yarovoi , it will help.

Sum, will return the total number of binary trees.

for example, if we take n=3, so in the for loop,

i=1, find_no(0)*find_no(2) ie taking first element as the root, there are 0 element in the left and 2 element in the right.

then recursively for 2 element it'll break the same way.for:

i=1,find_no(0)*find_no(1)=1*1=1 (ie first element root,0 element left 1 right)

i=2, find_no(1)*find_no(0)=1*1=1

so sum=1+1=2

so for n=3 and i=1:

find_no(0)*find_no(2)=1*2=2

for i=2:(taking 2nd element as root node)

find_no(1)*find_no(1)=1*1=1

for i=3:(taking 3rd element as root node)

find_no(2)*find_no(1)=2*1=2

so sum=2+1+2=5

which is true as you can check.

I agree with Bugaboo.

Even if conceptually the recursion is the same, computing the sum is much easier than actually generating the trees, because you don't have to think about proper structures.

Moreover, if you just have to compute the sums, this is more efficient:

```
int find_no(int n) {
int num=1, den=1;
for (int k=2; k<=n; ++k) {
num *= (n+k);
den *= k;
}
return num/den;
}
```

/**

* @author jk

* Given an inorder traversal only for a binary tree (not

* necessarily a BST), give a pseudo code to generate all possible

* binary trees for this traversal sequence. Firstly, how many binary

* trees can be generated given an in-order traversal?

*/

public class G99AllPosibleBST {

/**

* Catalan Number Formula : C[n] = SUM {i=1..n}(C[i-1]*C[n-i]) CN =

* (2n!)/((n!)*(n+1)!);

* Time Complexity =O(4^n) ; n = number of nodes

*/

public static int countSubtreeNumberBinaryTreeRecursive(int n) {

if (n == 0)

return 1;

int sum = 0;

for (int i = 1; i <= n; i++) {

sum += countSubtreeNumberBinaryTreeRecursive(i - 1) * countSubtreeNumberBinaryTreeRecursive(n - i);

}

return sum;

}

static int[] t = new int[512];

/**

* @param n : number of the nodes in the binary tree

* @returns the Catalan number;

* Time Complexity O(n*n)

*/

public static int countSubTreeBinaryTreeDP(int n) {

if (t[n] != 0)

return t[n];

t[0] = 1;

for (int i = 1; i <= n; i++) {

t[n] += countSubTreeBinaryTreeDP(i - 1)

* countSubTreeBinaryTreeDP(n - i);

}

return t[n];

}

/**

* @param args

*/

public static void main(String[] args) {

System.out.println(countSubtreeNumberBinaryTreeRecursive(10));

System.out.println(countSubTreeBinaryTreeDP(10));

}

}

```
def buildAllBST(a, low, hi): # hi is exclusive
if hi == low:
return [None]
elif hi - low == 1:
return [new Node(a[l], None, None)]
else:
bsts = []
for i in range(low, hi):
leftlist = buildAllBST(a, low, i)
rightlist = buildAllBST(a, i+1, hi)
for j in range(len(leftlist)):
l = leftlist[j]
for k in range(len(rightlist)):
r = rightlist[k]
bsts.append(new Node(a[i], l, r))
return bsts
```

This is my best DP solution:

```
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
struct Node {
Node *left;
Node *right;
};
typedef vector<Node *> Tree_Vector;
vector<Tree_Vector> trees;
// Build all the trees of order n
void build_trees(int n) {
Tree_Vector new_forest;
for (int i=1; i<=n; ++i)
for (Tree_Vector::const_iterator l = trees[i-1].begin(); l != trees[i-1].end(); ++l)
for (Tree_Vector::const_iterator r = trees[n-i].begin(); r != trees[n-i].end(); ++r) {
Node *newnode = new Node();
new_forest.push_back(newnode);
newnode->left = *l;
newnode->right = *r;
}
trees.push_back(new_forest);
}
int
main(int argc, char **argv) {
if (argc<2) exit(1);
int N = atoi(argv[1]);
Tree_Vector tmp;
// Initialize the N=0 case
tmp.push_back(NULL);
trees.push_back(tmp);
// DP computing of all levels up to N
for (int i=1; i<=N; ++i) {
build_trees(i);
}
// for (Tree_Vector::iterator l = trees[N].begin(); l != trees[N].end(); l++) {
// Tree(*l).print();
// cout << endl;
// }
}
```

It's space efficient, in the sense that every common sub-tree is stored just once. Still, the number of trees grows exponentially with n: O( (4^n)/(n^(3/2)) ) and so does the space needed to store all the trees.

With n = 16 my pc with 1GB of RAM already starts thrashing...

I'm afraid that to have a usable program, one have to generate one tree, print it out, discard it and then move onto the next one.

Anybody has an idea on how to do that?

P.S. If you want to test the code, just uncomment the last 'for' cycle and add the 'Tree' class:

```
struct Tree {
Node *root;
Tree(Node *r = NULL) : root(r) {};
int get_value(Node *n, const int base=0) {
if (n == NULL) return 0;
int count = base + 1;
count += count_nodes(n->left);
return count;
};
int count_nodes(Node *n) {
if (n == NULL) return 0;
int count = 1;
if (n->left) count += count_nodes(n->left);
if (n->right) count += count_nodes(n->right);
return count;
};
void print() { print_tree_r(root, 0); };
private:
void print_tree_r(Node *n, int base) {
int r = get_value(n, base);
cout << "(" << r << " <";
if (n->left) cout << get_value(n->left, base);
else cout << "-";
cout << ", ";
if (n->right) cout << get_value(n->right, r);
else cout << "-";
cout << ">) ";
if (n->left) print_tree_r(n->left, base);
if (n->right) print_tree_r(n->right, r);
}
};
```

Naive solution would be to get the permutations and insert, here is mine, which treats it as a subproblem recursively (the toughest is to figure out when to print... just do it in the last inserted, which is rightmost, or its left subtree)

```
void binST::makeTrees(const size_t max)
{
std::vector<int> N;
for (size_t idx = 1; idx <= max; ++idx)
N.push_back(idx);
makeTrees(mRoot, N, 0, N.size()-1, true);
}
void binST::makeTrees(node*& n, const std::vector<int>& N, size_t low, size_t high, bool print)
{
for (size_t i = low; i <= high; ++i)
{
if (n)
delete n;
n = new node(N[i]);
if (low == high && print)
printLevelOrder();
else
{
if (i > low)
makeTrees(n->left, N, low, i-1, i >= high);
if (i < high)
makeTrees(n->right, N, i+1, high, true);
}
}
}
```

I wonder whether this question is a real 'Google' interview question.

Because:

(1) The following description in the question is non-sense:

I know that given 'n' nodes, number of BTs possible is (2^n)-n.

(2) In Google's "Coaching Session: Tech Interviewing",

it says that "Don't use pseudo code - we want actual code".

It's strange that a Google interviewr asks you to give a pseudo code.

Remember, whenever the questions are real questions, people typically write them down from memory. You can't expect a flawless description. The core of the question might have been real, but it may be interspersed with comments from the person who posted the question. That person was probably unable to figure out the algorithm during the interview, so they came here to post the question and ask for pseudocode, all with the goal of understanding what approach they should have taken.

Hey Manan,

Computing the number of BTs possible was just a sub-question. The problem was to generate all possible BTs.

Sorry guys Here is the solution for making Trees

static ArrayList<TreeNode> MakeBTs(String str){

if(str.length() == 0)

return null;

ArrayList<TreeNode> btlist = new ArrayList<TreeNode>();

if(str.length() == 1){

btlist.add(new TreeNode(str.charAt(0)));

return btlist;

}

if(str.length() == 2){

TreeNode p = new TreeNode(str.charAt(0));

p.right = new TreeNode(str.charAt(1));

btlist.add(p);

TreeNode q = new TreeNode(str.charAt(1));

q.left = new TreeNode(str.charAt(0));

btlist.add(q);

return btlist;

}

for(int i=0;i<str.length();i++){

ArrayList<TreeNode> left = MakeBTs(str.substring(0,i));

ArrayList<TreeNode> right = MakeBTs(str.substring(i+1));

if(left==null && right==null){

btlist.add(new TreeNode(str.charAt(i)));

}else if(left!=null && right!=null){

for(TreeNode l:left){

TreeNode p = new TreeNode(str.charAt(i));

p.left = l;

for(TreeNode r:right){

p.right = r;

btlist.add(p);

}

}

}else{

if (right != null) {

for (TreeNode r : right) {

TreeNode p = new TreeNode(str.charAt(i));

p.right = r;

btlist.add(p);

}

}else if(left!=null){

for (TreeNode l : left) {

TreeNode p = new TreeNode(str.charAt(i));

p.left = l;

btlist.add(p);

}

}

}

}

return btlist;

}

The logic is here.

For example we have "abc", Now parse through string character by character.

For a :- make "a" the root, call "MakeBTs(bc") for right subtrees, which will produce two tree combination., SO for a we will have two BTs

For b: make "b" the parent,now call MakeBTs("a" for left subtrees and call MakeBTs("b") for right sub trees, this will produce 1 BT.

Similarily for c we will have 2 BTs.

Hope its clear now.

you code is totally unreadable !!

Did you make use of any memoization? What is the run time complexity of your code?

@Manan - What is your terminating condition in recursion so that you can print the tree at that time....

I have worried ..here not about recursions..but I am not able to find the point/conditions when I should print the tree..

I think you understood my confusion...

Pick an index in the in-order traversal sequence as the root. Then, generate all possible left subtrees whose in-order traversal is exactly all of the numbers before the root in the sequence and all possible right subtrees whose in-order traversal is the numbers after the root (do this recursively). All the possible trees with the chosen root are every combination of a right subtree and a left subtree. Do this for every possible index as the root, and you have every possible tree.

- eugene.yarovoi on December 28, 2011 Edit | Flag ReplyIf you want to count the number:

Trees(N) = Trees (N-1)*Trees(0) + Trees (N-2)*Trees(1) + ... + Trees(0)*Trees(N-1)

Trees(0) = 1

Trees(1) = 1

This can be evaluated using dynamic programming.