CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Interview Question


Country: India



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

Because the structure of the tree is defined, I feel the number of ways to populate the tree can't be more than one.

- cooldaa January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about below example..
example : 1 3 7 9 11 15


7


3 11



1 9 15



9



3 11



1 7 15

- sanjay.2812 January 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you were to draw the trees on paper, they do look different, so this example doesn't disprove anything.

- eugene.yarovoi January 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The examples form different trees. Try to make them on paper.

- cooldaa February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@cooldaa thanks..
@eugrne : See by your self one tree is has 7 as root and other has 7 as leaf. how do you explain them as same??

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

the answer is correct for completely balanced tree but not a tree which is not completely balanced.

In general I think the expression is
2^(int)((log n)+1) - n


for n=7 int(log7)+1=3
so 2^3-7=1 that is only one possibility.

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

Also see the below example.. to prove my point

1 2 3 4

{
   2
 /   \
1     3
       \
	4

     2
   /   \
  1     4
       /
      3


     3
    / \
   2   4
  /
 1



  3
 / \
1   4
 \
  2

}

- sanjay.2812 February 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could there be more than one way?

- Polymorpher January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there will be only one way to do this.

- hitesh January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there will be only one way to do this.

- hitesh January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there will be only one way to do this.

- hitesh January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there will be only one way to do this.

- hitesh January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there will be only one way to do this.

- hitesh January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there will be only one way to do this.

- hitesh January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there will be only one way to do this.

- hitesh January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

only one tree as the structure of the binary tree is defined..... otherwise (2 raised to n) -n..... as for every structure BST is possible.....

- Anonymous January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

only one possible, as the BT is fixed, and in order to make it BST, the elements need to be sorted, even if the elements are duplicate,the tree will still look same as the nodes are fixed.

- nutcraker January 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer is one

- kaushik May 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer is one

- kaushik May 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Ans: (n+1) * (2nCn), where n is the number of nodes.
Explanation: A unique tree can made from its inorder permutation along with a preorder or postorder permutation. Suppose its preorder permutation is 1,2,3,....,n then distinct binary trees can be formed using inorder permutation in "n!" ways.
For further details refer "Fundamentals of Data structures by Horowitz and Sahni". The chapter on trees gives full detail about this question.

- Karthik Sharma January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but the unique structure of the tree is already defined. This will give to distinct binary tree structures.

- cooldaa January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Take an example of 2 nodes only how many tree can be formed. I think only four.So above formula is wrong even in this case.
and as the structure is already fixed there would be only one way to populate the tree.

- BSG January 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Take an example of 2 nodes only how many tree can be formed. I think only four.So above formula is wrong even in this case.
and as the structure is already fixed there would be only one way to populate the tree.

- BSG January 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Little typo in the formula..... it should be
(1/(n+1))* (2nCn).

- Karthik February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Ans: (n+1) * (2nCn), where n is the number of nodes.
Explanation: A unique tree can made from its inorder permutation along with a preorder or postorder permutation. Suppose its preorder permutation is 1,2,3,....,n then distinct binary trees can be formed using inorder permutation in "n!" ways.
For further details refer "Fundamentals of Data structures by Horowitz and Sahni". The chapter on trees gives full detail about this question.

- Karthik Sharma January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But with the given unlabeled binary tree isn't the pre-order and inorder traversal has been fixed so that there can be only 1 unique tree possible

- deepak January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Deepak: yes each binary tree has fixed inorder and pre order traversals but keeping inorder fixed and taking all possible permutations of preorder traversal produces a new binary tree every time.

- Karthik February 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int numberOfTrees(int n)
{
	int a[1000];
	a[0]=0;
	a[1]=1;
	a[2]=2;
	for(int i=3; i<=n ;i++)
	{
		a[i]=0;
		for(j=0; j<i ;j++)
		{
			a[i]= a[i]+ a[j]*a[i-j-1]
		}
	}
	return a[n];
}

- Wayne January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think it may be 2^upper(ln(n))- n where n is the size of array

for example : 1 3 7 9 11 15

7

   3   11

1     9   15


    9

  3    11

 1 7     15

- sanjay.2812 January 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

whoever don't agree please put your comment for improvement..
I agree that there is only one possibility for complete binary tree that my expression is also giving ..there were not given that the array will make complete binary search tree.
I have given the solution on general level and it is correct. please provide me example to make it wrong. I will accept it...
but the examples I took.. my expression is satisfying ..

- sanjay.2812 February 02, 2012 | Flag


Add a Comment
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.

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