How to build a binary search tree with python without pointers?

Question

I have seen some answers to the question "how to build a binary tree", but the relate answers seem not to work!! They are based on algorithms more or less like this:

def insert(item, tree):
    if (item < tree.entry):
        if (tree.left != None):
            insert(item, tree.left)
        else:
            tree.left = Tree(item)
    else:
        if (tree.right != None):
            insert(item, tree.right)
        else:
            tree.right = Tree(item)

The code mentioned before has been written by Isaac1000, but other ones are very similar. The problem is that when tree.right or tree.left is passed to the function "insert" in the following calls:

insert(item, tree.left)
insert(item, tree.right)

the ones who wrote the code think to pass the reference, instead of a copy of the value, so that, tree.left or tree.right will not be really changed. Finally, that function or similar just work at the first or zero level of the Tree, but not at the n level of the tree. So, how to build a binary search tree without pointers?

P.S. I said "without pointers" just because I know that python hasn't got pointers, but please tell me if I'm wrong

@qfiard

"If you pass a mutable object into a method, the method gets a reference to that same object and you can mutate it to your heart's delight, but if you rebind the reference in the method, the outer scope will know nothing about it, and after you're done, the outer reference will still point at the original object."(Blay Conrad)

That speech made me all clear. I have understood that my code didn't word because I was used to rebind tree.left. The following code was the code I have been using till now:

    def insert(self, data):
        if self is None:
            self = Tree(data)
        else:
            if data < self.data:
                Link.insert(self.left, data)
            else:
                Link.insert(self.right, data)

Finally, when I wrote self = Tree(data) I was trying to rebind an object and the outer scope didn't know nothing about it. Instead, using the procedure I have posted, when I use self.right or self.left I try to modify the object without rebinding, so that the outer scope remembers my changes.

score 3 · Accepted Answer · edited May 23 '17 at 11:50

Arguments in Python are passed by assignment, which is similar to passing arguments by reference for mutable types (lists, objects, ...). See this stackoverflow answer for more details on the subject: https://stackoverflow.com/a/986145/2887956 .

The code that you provided works therefore perfectly if you use objects to represent your trees. The following code outputs

<<None, 0, None>, 1, <None, 2, None>>

class Tree(object):

  def __init__(self, entry):
      self.entry = entry
      self.left = None
      self.right = None

  def __str__(self):
      return '<%s, %d, %s>' % (self.left, self.entry, self.right)

def insert(item, tree):
    if item < tree.entry:
        if tree.left is not None:
            insert(item, tree.left)
        else:
            tree.left = Tree(item)
    else:
        if tree.right is not None:
            insert(item, tree.right)
        else:
            tree.right = Tree(item)

root = Tree(1)
insert(0, root)
insert(2, root)
print root

Your algorithm would also work if you used lists to represent your trees, although you would need to modify it substantially.

How to build a binary search tree with python without pointers?

1 Answers1