Explanation for apparent discrepancy in function call

Question

I am puzzled by the way a certain function (tree_insert) is invoked in Python code. It appears to me that its signature is being violated in the invocation. Can someone clarify? To be specific, tree_insert has arguments self and data. But, in the invocation, the first argument is data and the second is self.left. There appears to be an inconsistency, and yet the code works.

Python not defined recursive function?

class BinaryTree():
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def tree_insert(self, data):
        if (data < self.data):
            if (self.left != None):
                self.tree_insert(data, self.left)
            else:
                self.left = BinaryTree(data)
        else:
            if (self.right != None):
                self.tree_insert(data, self.right)
            else:
                self.right = BinaryTree(data)

The function works correctly despite an apparently incorrect way of invocation. There is some Python peculiarity at play here..

That will throw an error if you actually try to run it. So, yeah, it’s wrong. — deceze, Aug 24 '19 at 11:31
Try `b = BinaryTree(3); b.tree_insert(4); b.tree_insert(5)` and you will get `TypeError: tree_insert() takes 2 positional arguments but 3 were given` — Thierry Lathuille, Aug 24 '19 at 11:32
Do not write `if (self.left != None):`; write `if self.left is not None:`. No additional parentheses, and use `is` for the comparison to `None`. — Tordek, Aug 24 '19 at 11:34

cdlane · Accepted Answer · 2019-08-25T04:44:20.033

The code in that (6x) upvoted, and accepted answer simply doesn't work. When run it generates the error:

TypeError: tree_insert() takes 2 positional arguments but 3 were given

As you spotted, this call makes little sense:

self.tree_insert(data, self.left)

It should have been:

self.left.tree_insert(data)

Here's the corrected code:

class BinaryTree():
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def tree_insert(self, data):
        if data < self.data:
            if self.left:
                self.left.tree_insert(data)
            else:
                self.left = BinaryTree(data)
        else:
            if self.right:
                self.right.tree_insert(data)
            else:
                self.right = BinaryTree(data)

Some test code:

if __name__ == "__main__":
    from random import sample

    data = sample(range(-10, 11), 21)

    tree = BinaryTree(data.pop())

    for item in data:
        tree.tree_insert(item)

And if we borrow (and adapt) the display() code from this answer, we get binary trees something like:

> python3 test.py
                      __3_____   
                     /        \  
           __________0      __9_ 
          /           \    /    \
  _______-6_____      1    6_  10
 /              \      \  /  \   
-10___       __-3___   2  5  8   
      \     /       \    /  /    
     -8_   -5_     -1    4  7    
    /   \     \   /              
   -9  -7    -4  -2              
>

As the author of the original question I can confirm that I fixed this mistake once I spotted it, I was learning python at the time and didn't understand all of the syntax. Good answer. — Alexander Freyr, Nov 29 '19 at 20:33

Explanation for apparent discrepancy in function call

1 Answers1