shishir wrote:
> Hi,
> I am looking for a method for left to right insertion in a binary tree(
> mind it, its not BST am talking about). A simple binary tree where
> every root has not more than two childs and the insertion is always
> done starting from the leftmost side of any given node.
>
> 13
> / \
> 27 54
> / \ / \
> 23 42
>
> For eg in the above case the next node should be inserted as the left
> most child of 54.
> Let me know if there's any doubt regarding the question.
>
> ~Shishir
Is it possible for you to keep a count of the number of inserts already
made? If this can be done, then I think I have a simple solution of the
path to be taken. I already saw a function that uses bit shifting, I am
not sure if this is the same.. Consider the tree like this...
1
/ \
2 3
/ \ / \
4 5 6 7
where the numbers represent the insert number (that is, if you are
inserting the nth element, n is the insert number).
Then from the first bit that is one(excluding that bit).. use this for
decision.. 0 implies left subtree and one implies a right subtree.
If it is the 4th insert 4 = 100 - exclude the first one 00 left twice
leads to the 4th insert position
If it is the 7th insert 7 = 111 - exclude the first one, 11 is right
subtree twice.
HTH...
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
