Creating a binary tree from a binary sequence in python

Question

I am trying to binary create a tree from a binary sequence like "100101" then i want the tree to be created like this. (Basically 1 means go to the right and 0 means go to the left)

                                <Root node>
                                    |
                                    1
                                   /
                                  0
                                 /
                                0
                                 \
                                  1
                                 /
                                0
                                 \
                                  1

so i did it here is the code: where the value would be the string sequence (ex value = "1001")

def _inserto(root,value):
    for i in value:
        if root == None:
            root = BSTNode(i)
            current = root
        elif i == "1":
            if current.right is not None:
                current.right = BSTNode(i)
                current = current.right
            else:
                current.right = BSTNode(i)
                current = current.right
        elif i == "0":
            if (current.left is not None):
                current.left = BSTNode(i)
                current = current.left
            else:
                current.left =BSTNode(i)
                current = current.left
    return root

Now the problem is that if i want to input another sequence like "01", the tree should look like this

                            <Root Node>
                                |
                                1
                               /
                              0
                             / \
                            0   1
                             \
                              1
                             /
                            0
                             \
                              1

, but i am really having a hard time, since my function is going to over-write the old tree.

What part of this, exactly is problematic? You can keep an external reference to the last node in python just as well. You know python has classes and objects too? — Marcin
– Marcin, Commented Jul 22, 2012 at 20:46
"Basically 1 means go to the right and 0 means go to the left" Err... from your diagram it seems that 1 means go left. Is your diagram wrong, or am I reading it the wrong way? — Mark Byers
– Mark Byers, Commented Jul 22, 2012 at 20:46
@MarkByers I'm sharing your "err..." between the diagram and the code for _insert - Start with an intial root of 1, next is 0 < 1 so it goes left, but then 0 is not < 0, so it should go right (but is shown as going left)... I'm hoping the OP can clarify which of the three possible results is actually desired. — Jon Clements
– Jon Clements, Commented Jul 22, 2012 at 21:04
i am assuming we start with a initial empty tree, and when i insert a value, i look at it, if its a 0, it goes to the left and if its a one it goes to the right — Wobblester
– Wobblester, Commented Jul 22, 2012 at 22:25

Simon Callan · Accepted Answer · 2012-07-22 23:17:28Z

2

The problem is with the code dealing with an existing node. If it is present, the code overwrites it with a new BSTNode, losing all the existing nodes under it. What you need is something like:

    elif i == "1":
        if current.right is None:
            current.right = BSTNode(i)
        current = current.right
    elif i == "0":
        if root.left is None:
            current.left = BSTNode(i)
        current = current.left

This will only allocate a node if there is not one already present, and then set current to this new node.

answered Jul 22, 2012 at 23:17

Simon Callan

3,1301 gold badge24 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Creating a binary tree from a binary sequence in python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related