retrieve from a binary search tree

Question

I'm working on a binary search tree in python. But my retrieve method isn't working as I want to. It only returns the correct value when I want to retrieve the root, and returns none for all the other nodes.

Here's my code for my node class:

class Treenode:
    def __init__(self, item=None, left=None, right=None):
        self.item = item
        self.pleft = left
        self.pright = right
        self.parent = None

    def __str__(self):
        return str(self.item)

Code for my Binary Tree:

from Treenode import *
class Bintree:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, item):
        self.size += 1
        if self.root == None:
            self.root = Treenode(item)
        else:
            self.insertnode(self.root, item)

    def insertnode(self,node,item):
        if node.pleft == None and node.pright == None:
            if item > node.item:
                newnode = Treenode(item)
                node.pright = newnode
                newnode.parent = node
            else:
                newnode = Treenode(item)
                node.pleft = newnode
                newnode.parent = node
        else:
            if item > node.item:
                if node.pright != None:
                    self.insertnode(node.pright, item)
                else:
                    newnode = Treenode(item)
                    node.pright = newnode
                    newnode.parent = node 
            else:
                if node.pleft != None:
                    self.insertnode(node.pleft, item)
                else:
                    newnode = Treenode(item)
                    node.pleft = newnode
                    newnode.parent = node                  

    def print_inorder(self, root):
        if root == None:
            pass
        else:
            self.print_inorder(root.pleft)
            print(root.item)
            self.print_inorder(root.pright)

    def print_postorder(self, root):
        if root == None:
            pass
        else:
            self.print_postorder(root.pleft)
            self.print_postorder(root.pright)
            print(root.item)

    def print_preorder(self, root):
        if root == None:
            pass
        else:
            print(root.item)
            self.print_preorder(root.pleft)
            self.print_preorder(root.pright)

    def retrieve(self, node, item):
        if node == None:
            return 'Empty Tree'
        else:
            if node.item == item:
                return str(node)
            elif node.item > item:
                self.retrieve(node.pleft, item)
            elif node.item < item:
                self.retrieve(node.pright, item)

So the last method in Bintree returns None for all values except the Root, but it should return the value of the node.

populating the tree:

import BinTree
t = BinTree.Bintree()
t.insert(10)
t.insert(8)
t.insert(15)
t.insert(2)
t.insert(0)
t.insert(25)
t.insert(1)
t.insert(10)
t.print_preorder(t.root)
print('-----------------------')
t.print_inorder(t.root)
print('-----------------------')
t.print_postorder(t.root)
print('-----------------------')
temp = t.retrieve(t.root, 10)
print(temp)

The retrieve method only works for t.retrieve(t.root, 10), but not for any of the other values, when another value is given the method returns None — KenM
Post your code that populates your tree. Also, just an FYI, in your insertnode method last but one line says 'node.pleft = newNode'. newNode should be newnode. Finally indent your code properly in your question. — user3885927

user3885927 user3885927 · Accepted Answer · 2014-11-11T00:13:36

Your problem is you are not returning the value in all the paths of your code, hence you are seeing none. Printing something that doesn't return a value, prints None. Change your retrieve method like this:

def retrieve(self, node, item):
    if node == None:
        return 'Empty Tree'
    else:
        if node.item == item:
            return str(node)
        elif node.item > item:
            return self.retrieve(node.pleft, item)
        elif node.item < item:
            return self.retrieve(node.pright, item)

retrieve from a binary search tree

1 Answers