Public Group

# general question about binary trees

This topic is 5024 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

just a general question out of curiosity, is it possible to have only a RIGHT sub-tree? like, can a tree have just a right sub-tree, or is it that you can't have a right sub-tree without first having a left sub tree? hope that's a valid question that makes sense, thanks.

##### Share on other sites
search tree on paper and pencil to see how it works.

##### Share on other sites
No can't say i understand you. Are you meaning that you want only one right sub-node for each node? ...that wouldn't be a tree but rather a list, no.
I think you have to elaborate a bit further [smile]

EDIT: Ok, i'm oficially lost...

##### Share on other sites
It is possible, depending on how you build the tree (as Simian mentioned already). This is not a good thing, though, as it generates the absolute worst-case performance for a binary tree (it's basically a linear list, as Android_s mentioned).

Why is is so bad? The whole idea behind a binary tree is that which each decision, you divide the problem space by 2: every time to go to either the right or left node, you have effectively ignored all those on the other side. This makes searching rather fast. In the case you mention, you're never ignoring any nodes, just moving on to the next one.

This situation is avoided either by carefully building the tree (by sorting the nodes before you add them), or by using a 'self-balancing' binary tree. This is a binary tree that alters itself everytime a node changes in an attempt to keep an equal number of nodes on each side. Lots of info on this on the web.

Enough? Too much? Confused? Good!

##### Share on other sites
Having unbalanced nodes is a part of every type of tree data structure. Consider the case where you only have two nodes for example. The head node can only have one child.

However, there is a certain tree type called an AA-Tree, in which you can never have a left child without having a right child. In this case, it merely limits the possible combinations of tree structures to those which are not left-heavy.
All other types of trees allow more than one representation for the unbalanced cases.

1. 1
Rutin
32
2. 2
3. 3
4. 4
5. 5

• 12
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633314
• Total Posts
3011326
• ### Who's Online (See full list)

There are no registered users currently online

×