Member Avatar for 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.

Edited by jigglymig because: n/a
  • 2 Contributors
  • 4 Replies
  • 171 Views
  • 18 Hours Discussion Span
  • Latest Post Latest Post by mrnutty
Member Avatar for mrnutty

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

Member Avatar for 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

Edited by jigglymig because: n/a
Member Avatar for jigglymig

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

Member Avatar for 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]

Edited by mrnutty because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.