How to create a tree using a list of integers without overwriting previously entered values

Question

I'm trying to create a tree using a list or an array implementation of incoming integers. They need to be added to the tree as they're entered. The code below is what I have so far, but after around the 5th number entered, some of the previous elements are being overwritten. I'm unsure of how to correct this problem. I'm brand new to Python but have background knowledge in Java. I'm trying to learn how different data structures are implemented in other languages.

EDIT: Some sample input would be 6,8,3,9,2,1. They would be entered separately until a sentinel value was entered (in this case 'end'). The '$' are there to represent an empty element so if 6 was entered first, that would be the root. Then 8 would be its right child. If no numbers less than 6 were entered, the root's left child would be "$". Once the tree is printed using the above values, it should reflect the attached picture. Expected Output

binaryTree = ["$","$"];
counter = 0;

def update(user_input):        
    if(binaryTree[0] == "$"):  # set root
        binaryTree[0] = user_input;
        binaryTree.append("$");
        counter += 1;
    elif(binaryTree[counter] == "$"):  # if current element is empty

        if(user_input >= binaryTree[counter-1]):    # setting rightChild
            binaryTree.append("$");
            rightChild = ((counter - 1)*2)+2;
            binaryTree[rightChild] = user_input
        elif(user_input < binaryTree[counter -1]):  # setting leftChild
            binaryTree.append("$");
            leftChild = ((counter-1)*2)+1;
            binaryTree[leftChild] = user_input;
        binaryTree.append("$");
        counter += 1;
    else:                              # if current element is NOT empty
        if(user_input >= binaryTree[counter-2]):
            binaryTree.append("$");
            rightChild =((counter-2)*2)+2;
            binaryTree[rightChild] = user_input;
        elif(user_input < binaryTree[counter -2]):
            binaryTree.append("$");
            leftChild = ((counter-2)*2)+1;
            binaryTree[leftChild] = user_input;
        counter += 1;

Answer 1

If you're really just trying to insert "$" symbols into an array to fill out a binary tree level by level (but you really don't care about the ordering of the values in the tree, then this might be what you want:

import math


class BinaryTree(object):

    def __init__(self):
        self.binary_tree = ["$"]
        self.counter = 1
        self.height = 0

    def update(self, user_input):
        self.binary_tree[self.counter - 1] = user_input
        new_level = int(math.floor(math.log(self.counter + 1, 2)))
        if new_level > self.height:
            self.binary_tree.extend(["$"] * (2 ** new_level))
            self.height += 1
        self.counter += 1


bt = BinaryTree()
while True:
    i = int(input())
    bt.update(i)
    print(bt.binary_tree)

As you see, as each level is completed, the update function adds the right number of $ elements to fill out the next level:

$ python tree.py
1
[1, '$', '$']
1
[1, 1, '$']
1
[1, 1, 1, '$', '$', '$', '$']
1
[1, 1, 1, 1, '$', '$', '$']
1
[1, 1, 1, 1, 1, '$', '$']
1
[1, 1, 1, 1, 1, 1, '$']
1
[1, 1, 1, 1, 1, 1, 1, '$', '$', '$', '$', '$', '$', '$', '$']

The values of the elements are ignored, they're just placed into the tree as they're received, filling out each level before allocating the next. Random input looks the same:

$ python q.py
2
[2, '$', '$']
5
[2, 5, '$']
3
[2, 5, 3, '$', '$', '$', '$']
6
[2, 5, 3, 6, '$', '$', '$']
2
[2, 5, 3, 6, 2, '$', '$']
2
[2, 5, 3, 6, 2, 2, '$']
76
[2, 5, 3, 6, 2, 2, 76, '$', '$', '$', '$', '$', '$', '$', '$']
3
[2, 5, 3, 6, 2, 2, 76, 3, '$', '$', '$', '$', '$', '$', '$']

Given your example code, I think you actually want to create a min heap. If that's the case, you can still use this answer as a starting point, you'll just need to extend the functionality to add the comparisons and the swapping functions to maintain the heap property. Here's an example that adds a restore_heap function:

class BinaryTree(object):

    def __init__(self):
        self.binary_tree = ["$"]
        self.counter = 1
        self.height = 0

    def update(self, user_input):
        index = self.counter - 1
        self.binary_tree[index] = user_input
        new_level = int(math.floor(math.log(self.counter + 1, 2)))
        if new_level > self.height:
            self.binary_tree.extend(["$"] * (2 ** new_level))
            self.height += 1
        self.counter += 1
        self.restore_heap(index)

    def restore_heap(self, index):
        parent_index = (index - 1) / 2
        if parent_index < 0:
            return
        elif self.binary_tree[index] < self.binary_tree[parent_index]:
            tmp = self.binary_tree[parent_index]
            self.binary_tree[parent_index] = self.binary_tree[index]
            self.binary_tree[index] = tmp
        self.restore_heap(parent_index)

And as you see, this restores the heap after each insertion:

16
[16, '$', '$']
15
[15, 16, '$']
14
[14, 16, 15, '$', '$', '$', '$']
13
[13, 14, 15, 16, '$', '$', '$']
12
[12, 13, 15, 16, 14, '$', '$']
11
[11, 13, 12, 16, 14, 15, '$']
10
[10, 13, 11, 16, 14, 15, 12, '$', '$', '$', '$', '$', '$', '$', '$']
9
[9, 10, 11, 13, 14, 15, 12, 16, '$', '$', '$', '$', '$', '$', '$']
8
[8, 9, 11, 10, 14, 15, 12, 16, 13, '$', '$', '$', '$', '$', '$']