Google Interview Question

  • google-interview-questions
    0
    of 2 votes
    57
    Answers

    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?

    - Bugaboo on December 27, 2011 in United States Report Duplicate | Flag
    Google

Country: United States


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

- eugene.yarovoi on December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please post a pseudo code?

- Bugaboo on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on January 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
}

- jie on February 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi on February 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- victoriousvishal on September 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi on September 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sunny on December 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sunny on December 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- visu on January 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 on February 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi on February 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bp on September 19, 2013 | Flag
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.

- Anonymous on December 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi on December 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on January 10, 2012 | Flag
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?

- yangqch on December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yangqch on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Bugaboo on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yangqch on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

3
/
1
\
2

- yangqch on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Bugaboo on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
}

- yangqch on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1
\
3
/
2

- someone on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- yangqch on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What do you mean by Root.Max()?

- Anonymous on December 28, 2011 | Flag
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.

- yangqch on December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on January 03, 2013 | Flag
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

- bingjie3216 on December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on January 22, 2012 | Flag
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.

- someone on December 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- wave on December 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi on December 31, 2011 | Flag
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?

- Kira on January 07, 2012 | Flag Reply
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;
}

- gautam1237 on January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Bugaboo on January 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gautam1237 on January 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- david.rebatto@gmail.com on April 05, 2012 | Flag
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[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));

}

}

- Anonymous on January 14, 2012 | Flag Reply
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.

- Fentoyal on January 25, 2012 | Flag Reply
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

- SChokkalingam on January 28, 2012 | Flag Reply
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

- amshali on February 22, 2012 | Flag Reply
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[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?

- david.rebatto@gmail.com on April 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- david.rebatto@gmail.com on April 05, 2012 | Flag
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);
      }
   }
}

- Anonymous on May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

en.wikipedia.org/wiki/Catalan_number

- Anonymous on November 28, 2012 | Flag Reply
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.

- Alva0930 on February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi on February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey Manan,

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

- Bugaboo on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- loveCoding on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Victor on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- loveCoding on December 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on January 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- racseism on January 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

does everyone agreed on this solution that @Manan proposed?

- Andy2000 on September 18, 2012 | Flag


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More