wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> Simple Question -Number of distinct BSTs
        
(Message started by: mad on Mar 7th, 2008, 10:13pm)
Title: Simple Question -Number of distinct BSTs
Post by mad on Mar 7th, 2008, 10:13pm
Given n nodes, derive the number of distinct binary search trees that can be constructed from it.
Title: Re: Simple Question -Number of distinct BSTs
Post by towr on Mar 8th, 2008, 2:27am
Do the n nodes have distinct values?
Title: Re: Simple Question -Number of distinct BSTs
Post by mad on Mar 8th, 2008, 2:47am
I think it would be n! if thay are distinct, right?
Title: Re: Simple Question -Number of distinct BSTs
Post by towr on Mar 8th, 2008, 3:02am

on 03/08/08 at 02:47:00, mad wrote:
I think it would be n! if thay are distinct, right?
I think it would, generally, be less. Because different orders of insertion might still yield the same tree.

e.g. 31245 or 34512 should give the same tree (1,2 goes in the left subtree in both case; and 4,5 in the right)
Title: Re: Simple Question -Number of distinct BSTs
Post by mad on Mar 8th, 2008, 5:07pm
Q)Given the root of a binary tree and any two nodes in it, device an algorithm to find out the nearest ancestor to the given two nodes. Assume the tree has only left and right child pointers and no parent pointers.

[hide]Maybe we could mark the depth of each node and the do a dfs traversal visiting all nodes and say we get the string
1012, we take as ancestor the least value lying between the two required node values.
But, can anybody tell me how to mark depth at each node and what the complexity would be?
Is there a better method?[/hide]
Title: Re: Simple Question -Number of distinct BSTs
Post by mad on Mar 8th, 2008, 5:24pm
Another Question-

The structure of node of a binary tree is defined as

struct node
{
int info;
struct node *parent;
}


You are given pointers to two nodes of a tree and you have to find whether these two nodes lie on the same side of the root or not.

Achieve:
time - O(n)
space - O(1)
Title: Re: Simple Question -Number of distinct BSTs
Post by towr on Mar 9th, 2008, 3:46am

on 03/08/08 at 17:24:53, mad wrote:
The structure of node of a binary tree is defined as

struct node
{
int info;
struct node *parent;
}
The only thing known is the parent? Not even a left and right subtree?
Title: Re: Simple Question -Number of distinct BSTs
Post by Grimbal on Mar 9th, 2008, 6:31am
It is an ancestor's tree for people with a long tradition of being monoparental.
Title: Re: Simple Question -Number of distinct BSTs
Post by srikanth on Jul 10th, 2008, 6:09am

on 03/08/08 at 17:07:32, mad wrote:
Q)Given the root of a binary tree and any two nodes in it, device an algorithm to find out the nearest ancestor to the given two nodes. Assume the tree has only left and right child pointers and no parent pointers.

[hide]Maybe we could mark the depth of each node and the do a dfs traversal visiting all nodes and say we get the string
1012, we take as ancestor the least value lying between the two required node values.
But, can anybody tell me how to mark depth at each node and what the complexity would be?
Is there a better method?[/hide]


[hide]
1. Mark each node with corresponding depth (recursive DFS lets you mark depth easily, each level of recursion would increase depth by 1)
2. Do a Euler tour (DFS with repetition) of the tree and list the nodes. In this list, the node with least depth between the 2 nodes in question is the least common ancestor.
[/hide]
Title: Re: Simple Question -Number of distinct BSTs
Post by srikanth on Jul 10th, 2008, 6:31am

on 03/08/08 at 17:24:53, mad wrote:
Another Question-

The structure of node of a binary tree is defined as

struct node
{
int info;
struct node *parent;
}


You are given pointers to two nodes of a tree and you have to find whether these two nodes lie on the same side of the root or not.

Achieve:
time - O(n)
space - O(1)


Since we have access to parent , we could traverse back to the root and make note of root's child that is encountered on the way. Complexity would be O(log n ) in time and O(1) in space, did I miss something ?

[hide]
// returns true if nodes 'a' and 'b'
// are on the same side of root

bool
func(node *p, node *q){

node *a = p;
node *b = q;

// when the loop terminates, ((a->parent)->parent == NULL)
// we point to the child of root

while ((a->parent)->parent)
   a=a->parent;
}

while ((b->parent)->parent)
   b=b->parent;
}

// on our way back to root if we meet the same child of root
// then we must be on the same side of the root.
return (a == b)
}
[/hide]
Title: Re: Simple Question -Number of distinct BSTs
Post by towr on Aug 7th, 2008, 12:38am

on 08/06/08 at 21:23:17, acceleracer wrote:
Given n nodes, derive the number of distinct binary search trees that can be constructed from it.

it is 2^(n-1)
Try it for n=3. I get 5 distinct BSTs, not 4

(. 1 ( . 2 (3))
(. 1 ( (2) 3 .)
( (1) 2 (3) )
( (1) 2 . ) 3 .)
( (. 1 (2) ) 3 .)
Title: Re: Simple Question -Number of distinct BSTs
Post by acceleracer on Aug 7th, 2008, 8:10am
sorry it is ((2^n)-n)
Title: Re: Simple Question -Number of distinct BSTs
Post by SMQ on Aug 7th, 2008, 8:33am

on 08/07/08 at 08:10:58, acceleracer wrote:
sorry it is ((2^n)-n)

Sorry, still no.

(. 1 (. 2 (. 3 (4) )
(. 1 (. 2 ( (3) 4 .)
(. 1 ( (2) 3 (4) )
(. 1 ( (2) 3 .) 4 .)
(. 1 ( (. 1 (3) ) 4 .)
( ( (1) 2 .) 3 (4) )
( (. 1 (2) ) 3 (4) )
( (1) 2 ( (3) 4 .) )
( (1) 2 (. 3 (4) ) )
( (. 1 (. 2 (3) ) 4 .)
( (. 1 ( (2) 3 .) 4 .)
( ( (1) 2 (3) ) 4 .)
( ( (1) 2 .) 3 .) 4 .)
( ( (. 1 (2) ) 3 .) 4 .)

--SMQ
Title: Re: Simple Question -Number of distinct BSTs
Post by ankura on Aug 31st, 2008, 1:09pm
i think answer is  2n C n .
catelan number...
:D
Title: Re: Simple Question -Number of distinct BSTs
Post by javeed.shariff on Sep 16th, 2008, 10:27pm
Hint: how many x digits number can be formed using y numbers w/o repitations

Answer: yPx

Similarly considering at all levels we derive the following:

  r=n
-------
>      nP(r+1)
-------
 r = 0

ex: for n=3,

we can have 3P1 + 3P3 = 3+6 = 9 BST
Title: Re: Simple Question -Number of distinct BSTs
Post by towr on Sep 17th, 2008, 2:05am

on 09/16/08 at 22:27:48, javeed.shariff wrote:
Hint: how many x digits number can be formed using y numbers w/o repitations

Answer: yPx
What is P?


Quote:
ex: for n=3,

we can have 3P1 + 3P3 = 3+6 = 9 BST
We only get 5 distinct BSTs though.
I gave them all a few posts up.
Title: Re: Simple Question -Number of distinct BSTs
Post by SMQ on Sep 17th, 2008, 5:10am

on 09/17/08 at 02:05:07, towr wrote:
What is P?

At least as I've encountered it (and Mathworld agrees (http://mathworld.wolfram.com/Permutation.html)), nPk = k!http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifnCk = n!/(n-k)! is the number of distinct permutations of k elements chosen from a set of n distinct elements.

--SMQ
Title: Re: Simple Question -Number of distinct BSTs
Post by kumariitr on Nov 27th, 2008, 10:08am
let x(n) denote the number of distinct BSTs   for n elements (assumed that elements are distinct)

then for even n, x(n) = 2 [x(n-1)*x(0) + x(n-2)*x(1) +x(n-3)*x(2)+...upto (n-1)/2 terms] + [x((n-1)/2)]^2

and for odd n, x(n) = 2 [x(n-1)*x(0) + x(n-2)*x(1) +x(n-3)*x(2)+...upto n/2 terms]
Title: Re: Simple Question -Number of distinct BSTs
Post by towr on Nov 27th, 2008, 10:14am
But x(3)=5, which isn't even. And according to your formula it should be (considering the factor of 2 in the front)

You seem to have switched which is odd and which is even  :)
Title: Re: Simple Question -Number of distinct BSTs
Post by kumariitr on Nov 28th, 2008, 8:41am
correct series representing the solution is:

let x(n) denote the number of distinct BSTs   for n elements (assumed that elements are distinct)

then for odd n>1, x(n) = 2 [x(n-1)*x(0) + x(n-2)*x(1) +x(n-3)*x(2)+...upto (n-1)/2 terms] + [x((n-1)/2)]^2

and for even n, x(n) = 2 [x(n-1)*x(0) + x(n-2)*x(1) +x(n-3)*x(2)+...upto n/2 terms]

and x(1) = 1 and taking x(0) = 1.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board