Interview Question
Country: India
If you were to draw the trees on paper, they do look different, so this example doesn't disprove anything.
@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??
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.
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.
but the unique structure of the tree is already defined. This will give to distinct binary tree structures.
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.
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.
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.
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
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
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 ..
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