binary tree

[jigglymig]

I need to create ever possible binary tree and then count the comparisons

an example is if I had a binary tree with 1 and 2
then there are 4 possible binary trees...
root = 1
LChild = 2

root = 1
RChild = 2

root = 2
LChild = 1

root = 2
RChild = 1

Next I would compare, so if I inserted a 3rd item. the 3rd item would compare with the first tree 2 times at the root and 2 times with the LChild and so forth till the last one. I would then have 16 total comparisons (8*2)

My problem is I am having alot of trouble creating every possible tree without wanting to hardcode it... also I did some math to figure out if I had 3 elements my comparisons would be 180.

[mrnutty]

I'm not sure what exactly you are saying. What is a binary tree with 1 and 2? Maybe a picture would help.

[jigglymig]

one node is 1 and another node is 2.
so I would create ever possible tree with the 2 nodes
parent/root = 1
LeftChild = 2
1
/
2
parent/root = 1
RrightChild = 2
1
\
2
parent/root = 2
LeftChild = 1
2
/
1
parent/root = 2
RightChild = 1
2
\
1

this has been killing me ALL day so I would really really appreciate the help

[jigglymig]

well couldn't figure it out so I just used for loops and did it :/ thanks for looking at it though

[mrnutty]

The number of possible binary tree you can create is [tex]2^n[/tex] where n is the number of nodes. And for each one, you will do at max [tex]n[/tex] comparison when trying to insert a new element. Hence the maximum number of comparison for this problem will be [tex]2^n*n[/tex]