How to implement a binary search tree in Python?

Question

I am executing the below code, but not able to get the desired output:

class Node:

    rChild,lChild,data = None,None,None

    def __init__(self,key):

        self.rChild = None

        self.lChild = None

        self.data = key

class Tree:

    root,size = None,0

    def __init__(self):

        self.root = None

        self.size = 0

    def insert(self,node,someNumber):

        if node is None:

            node = Node(someNumber)

        else:

            if node.data > someNumber:

                self.insert(node.rchild,someNumber)

            else:

                self.insert(node.rchild, someNumber)

        return

def main():

    t = Tree()

    t.root = Node(4)

    t.root.rchild = Node(5)

    print t.root.data #this works

    print t.root.rchild.data #this works too

    t = Tree()

    t.insert(t.root,4)

    t.insert(t.root,5)

    print t.root.data #this fails

    print t.root.rchild.data #this fails too

if __name__ == '__main__':

     main()

Answer 1

Binary insertion Sort will help you to find the proper location to insert the picked up item at each iteration. Kindly refer to the below example of a binary insert:

class Node:

    def __init__(self, val):

        self.l_child = None

        self.r_child = None

        self.data = val

def binary_insert(root, node):

    if root is None:

        root = node

    else:

        if root.data > node.data:

            if root.l_child is None:

                root.l_child = node

            else:

                binary_insert(root.l_child, node)

        else:

            if root.r_child is None:

                root.r_child = node

            else:

                binary_insert(root.r_child, node)

def in_order_print(root):

    if not root:

        return

    in_order_print(root.l_child)

    print root.data

    in_order_print(root.r_child)

def pre_order_print(root):

    if not root:

        return        

    print root.data

    pre_order_print(root.l_child)

    pre_order_print(root.r_child)    

r = Node(3)

binary_insert(r, Node(7))

binary_insert(r, Node(1))

binary_insert(r, Node(5))

     3

    / \

   1   7

      /

     5

print "in order:"

in_order_print(r)

print "pre-order"

pre_order_print(r)

in order:

1

3

5

7

pre-order

3

1

7

5

 Want to become a Python Developer? Check out this insightful Python Certification course.