Author |
Topic: Simple Question -Number of distinct BSTs (Read 4719 times) |
|
mad
Junior Member
Posts: 118
|
 |
Simple Question -Number of distinct BSTs
« on: Mar 7th, 2008, 10:13pm » |
 Quote  Modify
|
Given n nodes, derive the number of distinct binary search trees that can be constructed from it.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #1 on: Mar 8th, 2008, 2:27am » |
Quote Modify
|
Do the n nodes have distinct values?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #2 on: Mar 8th, 2008, 2:47am » |
Quote Modify
|
I think it would be n! if thay are distinct, right?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #3 on: Mar 8th, 2008, 3:02am » |
Quote Modify
|
on Mar 8th, 2008, 2:47am, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #4 on: Mar 8th, 2008, 5:07pm » |
Quote Modify
|
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.
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?
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #5 on: Mar 8th, 2008, 5:24pm » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #6 on: Mar 9th, 2008, 3:46am » |
Quote Modify
|
on Mar 8th, 2008, 5:24pm, 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?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #7 on: Mar 9th, 2008, 6:31am » |
Quote Modify
|
It is an ancestor's tree for people with a long tradition of being monoparental.
|
|
IP Logged |
|
|
|
Colonel Panic
Newbie
Gender:
Posts: 9
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #8 on: Jul 10th, 2008, 6:09am » |
Quote Modify
|
on Mar 8th, 2008, 5:07pm, 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.
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? |
|
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.
|
|
IP Logged |
|
|
|
Colonel Panic
Newbie
Gender:
Posts: 9
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #9 on: Jul 10th, 2008, 6:31am » |
Quote Modify
|
on Mar 8th, 2008, 5:24pm, 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 ?
// 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)
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #10 on: Aug 7th, 2008, 12:38am » |
Quote Modify
|
on Aug 6th, 2008, 9:23pm, 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 .)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
acceleracer
Newbie
Posts: 2
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #11 on: Aug 7th, 2008, 8:10am » |
Quote Modify
|
sorry it is ((2^n)-n)
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #12 on: Aug 7th, 2008, 8:33am » |
Quote Modify
|
on Aug 7th, 2008, 8:10am, acceleracer wrote:
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
|
| « Last Edit: Aug 7th, 2008, 8:35am by SMQ » |
IP Logged |
--SMQ
|
|
|
ankura
Newbie
Posts: 1
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #13 on: Aug 31st, 2008, 1:09pm » |
Quote Modify
|
i think answer is 2n C n .
catelan number...
|
|
IP Logged |
|
|
|
javeed.shariff
Newbie
Posts: 2
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #14 on: Sep 16th, 2008, 10:27pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #15 on: Sep 17th, 2008, 2:05am » |
Quote Modify
|
on Sep 16th, 2008, 10:27pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #16 on: Sep 17th, 2008, 5:10am » |
Quote Modify
|
on Sep 17th, 2008, 2:05am, towr wrote:
At least as I've encountered it (and Mathworld agrees), nPk = k! nCk = n!/(n-k)! is the number of distinct permutations of k elements chosen from a set of n distinct elements.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
kumariitr
Newbie
Posts: 4
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #17 on: Nov 27th, 2008, 10:08am » |
Quote Modify
|
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]
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #18 on: Nov 27th, 2008, 10:14am » |
Quote Modify
|
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 
|
| « Last Edit: Nov 27th, 2008, 10:22am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kumariitr
Newbie
Posts: 4
|
|
Re: Simple Question -Number of distinct BSTs
« Reply #19 on: Nov 28th, 2008, 8:41am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print