Data structures in Python Series 6 : Implementing a Binary Tree

Implementing Binary Tree Step 1 | Binary Search Tree : 

The following is definition of Binary Search Tree(BST) according to Wikipedia

Binary Search Tree, is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes.
# -*- coding: utf-8 -*-

"""
Created on Sat Aug 18 00:39:52 2018
@author: zeus
"""
'''
First we define a structure for the nodes to be
        ________________________________

NODE = |left-pointer|value|right-pointer|

        ````````````````````````````````
'''
class Node:
    def __init__(self,key):
        self.left = None
        self.right = None
        self.val = key
'''
Now we are going  to define a class Binary tree ,
which will have

1.a default initialisation method,

2.a method to add nodes which would take the head pointer
as input and return the resultant head pointer

3.a method to print the binary tree out in inorder :
        Left value | middle value | right value|
'''
class Btree:

    def __init__(self,data=None):
        self.head = None
    def add(self,root,data):
        '''
        The root == None will end the recursive implementation
        '''
        if root == None:
            root = Node(data)
            return root
        else:
            if root.val < data:
                root.right = self.add(root.right,data)
                '''
          If value of the current node is less than data then pass the
          data to the right side of the current node as per BST property
          less values on left and greater one on right
                '''
            else:
                '''
          If value of the current node is greater than data then pass the
          data to the left side of the current node as per BST property
          less values on left and greater one on right
                '''
                root.left = self.add(root.left,data)
        return root         

    def inorder(self,root):
        if root:
            #will run until root == None i.e. end of the particular branch
            self.inorder(root.left)
            '''
traverse to the extreme left, now when extreme left == None print its value then print its parents value then print its right siblings value
            '''
            print(root.val)
            self.inorder(root.right)

if __name__ == "__main__":
    lis = Btree()
    lis.head=lis.add(lis.head,50)
    lis.head=lis.add(lis.head,30)
    lis.head=lis.add(lis.head,20)
    lis.head=lis.add(lis.head,40)
    lis.head=lis.add(lis.head,70)
    lis.head=lis.add(lis.head,60)
    lis.head=lis.add(lis.head,80)
    lis.inorder(lis.head)

'''
Output
20
30
40
50
60
70
80
'''