[Tutor] Of integers, relations and trees

[Tor Hildrum]

I have this problem which I thought would be trivial, but I can't
seem to figure out a decent way to do it.

Say I have the following file:
10
-100
-101
-103
-108
--1080
---1080.10
---1080.11
12
-120
-125
20
30
-300
--3010
---3010.3

These numbers represents a tree-like structure.

In lack of a better explanation, here is how it works:
A level in the tree follows the following:
x * 10^level

x * 10^1 belongs to level 1 in the three
x * 10^2 belongs to level 2 in the three.
etc.

So, the top-nodes in the three are 10, 12, 20 and 30.
The childs of 10 is 100, 101, 103 and 108.
The child of 108 is 1080.
The child of 1080 is 1080.10 and 1080.11 and these are the leaves.

I decided to make this pretty straightforward so I wrote a Node class
and a Tree class.
A Node has a key which is an integer, as well as some additional
information that isn't relevant to the structure. It also has a link
to it's sibling, which is the next node on the same level. And a link
to it's first child.

So for 10, it looks like this.:
10 -> 20  (siblings of 10)
 | (child)
100 -> 101 -> 103 -> 108 (siblings of 100)

Inserting a sibling is done like this:
-----------------------------------------------------
def addSibling(self, newNode):
    tmp = self.node # current node
    last = self.node # previous node

    # find the node that is the direct sibling to the new node
    while( tmp != None && tmp['key'] < newNode['key']):
      last = tmp
      tmp = tmp['sibling']

    # insert the new node after the node with a lower key
    last['sibling'] = newNode

    # If there is a node with a higher key, add it as a sibling to the new node
    if( tmp != None ):
      newNode['sibling'] = tmp
-----------------------------------------------------

This code does not handle a special case where the newNode has the
smallest key among the siblings and should be placed first and thus be
the direct child of the parent level. But, that doesn't really matter.

How do I know if I have a sibling or a child?
Simple, I just check the length:
---------------------------------------------
if( len(str(node1[key])) == len(str(node2[key])) ):
---------------------------------------------

If the length, amount of integers, is the same, they are siblings.

My problem is this:
Say I have created a new node with the key 2080.

I start of with my root node which has a key of 0. 2080 is not
a sibling of 0, so I call a recursive function named addChild().
addChild checks the child of 0, which is 10 and determines that
2080 is not a sibling of 10. But, it's not a child either.

Here comes my query:
How do I determine that 2080 is not a child of 10. Or how do i determine
that 536798 is not a child of 536780? And how do I determine that it is a child?

I'll try to explain again:
5.36798 * 10^5 is at level 5 in the tree.
It's direct children looks like this:
5.36798x * 10^6.
5.36797x * 10^6 is NOT a child, it is a child of 5.36797 * 10^5.
Does this make sense to anyone? :)

Also, consider the following:
5.36798xxx * 10^8

While this is not a direct child of 5.36798 * 10^5, it is a child of a
child and belongs in that subtree.

I can't seem to rack my brains around a solution for this. Maybe it's
my tree-structure that is making this more complex than it should be?