Binary Search tree without classes, but as list of lists

Question

How can one implement a BST without class structures, but as a list of list? I couldn't find such an implementation, so I tried it myself:

numbers = [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
tree = []

for num in numbers:
    tree.append( [num, 0, 0] )

for num in numbers[1:]:
    for l in tree:
        if num != l[0]:
            if num > l[0]:
                if l[2] == 0:
                    l[2] = numbers.index(num)
                    break
            else:
                if l[1] == 0:
                    l[1] = numbers.index(num)
                    break

The tree has one list for each element.

• tree[i][0] would be the value of the node.

• tree[i][1], tree[i][2] would be the index for the left and right node of the node at i.

This does sadly not work (no Error). With the example above, it would look like this (the root is at the left):

# [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
#
#          15
#         /  \
#        /    8
#      13
#     /  \
#    /    4
#   /
#  7
#   \       10
#    \     /  \
#     \   /    3
#      \ /
#       2
#        \   1
#         \ /
#          0

As you can see, the 10 became a left child of 2, while it should have been a right child of 13.

Answer 1

If I understand correctly you want the tree to be a list of triplets, where each triplet represents a node of the tree, consisting of [value, left, right], where left and right are indices in the overall list, referencing the relevant child node, or else 0.

The problem in your code is that you do not really traverse the tree along those parent-child relationships. Instead you just iterate it from left to right with for l in tree. Instead you should do l = tree[l[1]] or l = tree[l[2]] to go from parent to child node.

Secondly, it should never happen that num == l[0] (except for the root itself, which your code skips anyway), as that would mean that number had already been linked from a parent node and you have a duplicate. If this happens, the duplicate should be ignored, and you should exit the loop.

So here is the correction of your main loop:

for i, num in enumerate(numbers):
    l = tree[0]
    while num != l[0]:
        if num > l[0]:
            if l[2] == 0:
                l[2] = i
                break
            l = tree[l[2]]  # walk down to right child
        else:
            if l[1] == 0:
                l[1] = i
                break
            l = tree[l[1]]  # walk down to left child

Note that I used enumerate for the loop to avoid that you have to call index.

I would also suggest creating at least functions, and separating the logic for finding a value in the tree, from inserting a value. Also, naming could be improved:

VALUE = 0
LEFT = 1
RIGHT = 2

def find(tree, num):
    if not tree:
        return
    node = tree[0]
    while num != node[VALUE]:
        i = node[RIGHT if num > node[VALUE] else LEFT]  # index of child
        if i == 0:  # no child in that direction
            return node
        node = tree[i]
    return node

def insert(tree, num):
    if tree:
        node = find(tree, num)
        if num == node[VALUE]:
            return
        node[RIGHT if num > node[VALUE] else LEFT] = len(tree)
    tree.append([num, 0, 0])


numbers = [7, 2, 13, 0, 10, 15, 4, 1, 3, 8]
tree = []
for num in numbers:
    insert(tree, num)
print(tree)