Newbie inserting into binary tree checks

Question

I am learning about Binary Search trees and I don't understand why this code won't work for insert in to a binary search tree:

def insert(self, data, node):
    node_to_insert = Node(data)

    if node is None:
        node = node_to_insert
    else:
        if data < node.data:
            node.left = self.insert(data, node.left)
        else:
            node.right = self.insert(data, node.right)

I know this code works:

    def insert(self, data, node):
        node_to_insert = Node(data)

        if node is None:
            node = node_to_insert
        else:
            if data < node.data:
                if node.left is None:
                    node.left = node_to_insert
                else:
                    self.insert(data, node.left)
            else:
                if node.right is None:
                    node.right = node_to_insert
                else:
                    self.insert(data, node.right)

The way I see it is that the extra is None check should be done when the function is recalled no?

Also why does this work:

def print_inorder(self, node):
    if node is not None:
        self.print_inorder(node.left)
        print node.data
        self.print_inorder(node.right)

when it doesnt have the extra checks to see if node.left is None before calling self.print_inorder(node.left)

when you say something doesn't work, can you be more specific? does it error (and please copy/paste is the error) or does it return an unexpected result (and please copy/paste the result)...thanks! — jpwagner, Dec 02 '13 at 04:25
Neither insertion function works. The first one fails because it never returns anything to assign to `node.left` or `node.right`, but the second one still fails for insertion into an empty tree. [Read up on the `return` statement.](http://stackoverflow.com/questions/7129285/why-would-you-use-the-return-statement-in-python) — user2357112, Dec 02 '13 at 04:36
please don't use TABS for indenting (instead use 4 spaces) and read about pep8 before it's too late... — oz123, Dec 02 '13 at 06:31

score 0 · Answer 1 · answered Dec 02 '13 at 06:47

In your code:

if data < node.data:
    node.left = self.insert(data, node.left)
else:
    node.right = self.insert(data, node.right)

Your method self.insert returns None, so after the data is properly inserted into node.left or node.right, you are assigning None to them. Rather you want

if data < node.data:
    self.insert(data, node.left)
else:
    self.insert(data, node.right)

Newbie inserting into binary tree checks

1 Answers1