Geek Answers Handbook

Insert into binary search tree

Therefore, I need to insert the node into the binary search tree. In my introductory class, binary search trees are represented as linked lists, such as, [4, [5, [0, [],[]], [2, [], []]], [1, [],[]]]for this binary tree in the image below:

this binary tree.

(This is not a binary search tree, just a binary tree on which I had a photo).

So, to insert node into the tree, I wrote the following recursive code:

def tree_node(key):
    return [key, [],[]]

def insert(bst,key):
    if bst == []:
        return tree_node(key)
    if key < bst[0]:
        return insert(bst[1],key)
    else:
        return insert(bst[2],key)
    return bst

It just returns node, but not a new tree with node

For instance:

>>> insert([2, [1, [], []], [3, [], []]], 6)
[6, [], []]

when it should be:

>>> insert([2, [1, [], []], [3, [], []]], 6)
[2, [1, [], []], [3, [], [6, [], []]]]

Thank!

+4
source share
2 answers

. , list, , . slice :

def insert(bst,key):
    if bst == []:
        bst[:] = tree_node(key)
    elif key < bst[0]:
        insert(bst[1],key)
    else:
        insert(bst[2],key)

, . , return bst ( , ).

+2

return insert(bst[1],key) bst[1] = insert(bst[1],key) ( bst[2]); - return.

0

More articles:


All Articles