• 1

Country: United States

Comment hidden because of low score. Click to expand.
13
of 13 vote

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.

If 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.

Comment hidden because of low score. Click to expand.
0

Can you please post a pseudo code?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

the # of trees with same traversal should then equal
catalan numbers ? ie. C(2n,n)/(n+1) with n being the number of nodes

Comment hidden because of low score. Click to expand.
0

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
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

Sorry, that was a typo. I have corrected it above.

Comment hidden because of low score. Click to expand.
0

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) {
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;
}
}
}
return trees;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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!

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

this is C(2n,n)/(n+1) ..

Comment hidden because of low score. Click to expand.
0
of 4 vote

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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``````

Comment hidden because of low score. Click to expand.
0

I think u missed 3 . Using the inductive method, it will be easy to find.
/
1
\
2

Comment hidden because of low score. Click to expand.
0

3
/
1
\
2

Comment hidden because of low score. Click to expand.
0

Ah yes, can you give a pseudo code for your approach?

Comment hidden because of low score. Click to expand.
0

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

//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)
}
}

void main(){
int[] sequence=readInput();//suppose sequence is an array of integer
Node newNode=new Node(sequence);//put the first Node in

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

Comment hidden because of low score. Click to expand.
0

1
\
3
/
2

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

What do you mean by Root.Max()?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

It will be same for all the orders because trees will be same. Just order of traversal will change

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Nope, there are 5 cases in your 3,4,5 example.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

You don't actually use inorder anywhere (except to test if its size is 0, which won't work since you're not creating a sub-list anywhere). Check out my solution at the top of the page. It provides an easy DP approach to counting the number of trees.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if I am a retard, but I don't understand the question. Can anyone provide sample input and output?

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

-1 : The problem is to compute all the binary trees, not just the sum.

Comment hidden because of low score. Click to expand.
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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* @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;

/**
* @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 = 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));

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The number of all possible trees is
(2n)! / ((n+1)!*n!)
And I agree with eugene.yarovo on his DP method.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why this is so complicated?
Take a midpoint from inorder string and then recursively construct BST for the left side and then do the same for right side

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

en.wikipedia.org/wiki/Catalan_number

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Hey Manan,

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

Comment hidden because of low score. Click to expand.
0

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){
return btlist;
}
if(str.length() == 2){
TreeNode p = new TreeNode(str.charAt(0));
p.right = new TreeNode(str.charAt(1));
TreeNode q = new TreeNode(str.charAt(1));
q.left = new TreeNode(str.charAt(0));
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){
}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;
}
}
}else{
if (right != null) {
for (TreeNode r : right) {
TreeNode p = new TreeNode(str.charAt(i));
p.right = r;
}
}else if(left!=null){
for (TreeNode l : left) {
TreeNode p = new TreeNode(str.charAt(i));
p.left = l;
}
}
}
}
return btlist;
}

Comment hidden because of low score. Click to expand.
0

Can you please add logic/pseudo code too? The code is not very clear to me.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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...

Comment hidden because of low score. Click to expand.
0

does everyone agreed on this solution that @Manan proposed?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.