title: How to build a binary search tree with python without pointers?
body: <p>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:</p>
  
  <pre><code>def insert(item, tree):
      if (item &lt; 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)
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>insert(item, tree.left)
  insert(item, tree.right)
  </code></pre>
  
  <p>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>
  
  <p>P.S.
  I said "without pointers" just because I know that python hasn't got pointers, but please tell me if I'm wrong</p>
  
  <p>@qfiard</p>
  
  
  <p>"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)</p> 
  
  <p>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:</p>
  
  <pre><code>    def insert(self, data):
          if self is None:
              self = Tree(data)
          else:
              if data &lt; self.data:
                  Link.insert(self.left, data)
              else:
                  Link.insert(self.right, data)
  </code></pre>
  
  <p>Finally, when I wrote <code>self = Tree(data)</code> 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.</p>