Error in my BST using Lists

Question

I'm building a BST, however instead of using nodes to implement, I'm using lists. I built it with the same logic I've used in c++ and c#, however I'm getting an incorrect output. I've racked my head against this problem for a while now, but I just don't see anything that's "wrong". I should note that tree[0] is the node value, tree[1] is for the left subtree and tree[2] is the right subtree.

def insert(tree, value):
if tree == []:
    tree.append(value)
    tree.append([])
    tree.append([])
    return 0
else:
    if value == tree[0]:
        return -1
    elif value < tree[0]:
        if tree[1] == []:
            tree[1].append(value)
            tree[1].append([])
            tree[1].append([])
            return 0
        else:
            insert(tree[1],value)
    elif value > tree[0]:
        if tree[2] == []:
            tree[2].append(value)
            tree[2].append([])
            tree[2].append([])
            return 0
        else:
            insert(tree[2],value)

An example list of values to pass
['20', '10', '30', '5', '35', '8', '25', '2', '37', '8', '27', '15', '22']

Expected output:
[20, [10 ,[5 ,[2 ,[] ,[]], [8, [], []]], [15, [], []]], [30, [25, [22, [], []], [27, [], []]], [35, [], [37, [], []]]]]

Actual output:
['20', ['10', [], ['2', ['15', [], []], []]], ['30', ['25', ['22', [], []], ['27', [], []]], ['5', ['35', [], ['37', [], []]], ['8', [], []]]]]

I've tried tracing it as it runs, but even that looks like it should be correct

After posting this and re-reading, I noticed that my list provided is actually a list of strings, not integers. I think that may be my problem... I was reading from a file, and didn't think to convert the strings to ints. I'll update once I've re run if problem still exists — Podo
– Podo, Commented Jan 29, 2018 at 7:31
Heh, problem solved ;) So glad it was such a simple error! I was sure that my logic was correct. — Podo
– Podo, Commented Jan 29, 2018 at 7:33
Oops, didn't read your comments :) still simplified your approach. — user2390182
– user2390182, Commented Jan 29, 2018 at 7:56

user2390182 · Accepted Answer · 2018-01-29 08:05:25Z

1

Your code works fine, but can be simplified:

def insert(tree, value):
     if tree == []:
         tree[:] = [value, [], []]
         return 0
     if value == tree[0]:
         return -1
     return insert(tree[1:][value > tree[0]], value)

Your real problem is that your list contains strings that are sorted lexicographically ('15' does come before '2'!), but you expect them to be ordered as if they were integers:

>>> l = ['20', '10', '30', '5', '35', '8', '25', '2', '37', '8', '27', '15', '22']

>>> for x in l:
...     insert(tree, x)
# ['20', ['10', [], ['2', ['15', [], []], []]], ['30', ['25', ['22', [], []], ['27', [], []]], ['5', ['35', [], ['37', [], []]], ['8', [], []]]]]

You have to convert to int:

>>> for x in map(int, l):
...     insert(tree, x)
# [20, [10, [5, [2, [], []], [8, [], []]], [15, [], []]], [30, [25, [22, [], []], [27, [], []]], [35, [], [37, [], []]]]]

edited Jan 29, 2018 at 8:05

answered Jan 29, 2018 at 7:53

user2390182

73.7k6 gold badges71 silver badges95 bronze badges

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

1 Comment

Podo Over a year ago

can +1 for a simplified approach :) Very clean!

Collectives™ on Stack Overflow

Error in my BST using Lists

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related