Binary Search Tree

 

Create Root

We just create a Node class and add assign a value to the node. This becomes tree with only a root node.

 

class Node:

    def __init__(self, data):

        self.left = None

        self.right = None

        self.data = data

 

    def PrintTree(self):

        print(self.data)

 

root = Node(10)

root.PrintTree()

 

Inserting into a Tree

To insert into a tree we use the same node class created above and add an insert method to it The insert method compares the value of the node to the parent node and decides to add it as a left node or a right node. Finally, the PrintTree method is used to print the tree.

 

class Node:

 

    def __init__(self, data):

 

        self.left = None

        self.right = None

        self.data = data

 

    def insert(self, data):

# Compare the new value with the parent node

        if self.data:

            if data < self.data:

                if self.left is None:

                    self.left = Node(data)

                else:

                    self.left.insert(data)

            elif data > self.data:

                if self.right is None:

                    self.right = Node(data)

                else:

                    self.right.insert(data)

        else:

            self.data = data

 

# Print the tree

    def PrintTree(self):

        if self.left:

            self.left.PrintTree()

        print( self.data),

        if self.right:

            self.right.PrintTree()

 

# Use the insert method to add nodes

root = Node(12)

root.insert(6)

root.insert(14)

root.insert(3)

 

root.PrintTree()

 

 

Traversals of Binary Tree

# Inorder traversal

# Left -> Root -> Right

 

class Node:

 

    def __init__(self, data):

 

        self.left = None

        self.right = None

        self.data = data

# Insert Node

    def insert(self, data):

 

        if self.data:

            if data < self.data:

                if self.left is None:

                    self.left = Node(data)

                else:

                    self.left.insert(data)

            elif data > self.data:

                if self.right is None:

                    self.right = Node(data)

                else:

                    self.right.insert(data)

        else:

            self.data = data

 

# Print the Tree

    def PrintTree(self):

        if self.left:

            self.left.PrintTree()

        print( self.data),

        if self.right:

            self.right.PrintTree()

 

 

    def inorderTraversal(self, root):

        res = []

        if root:

            res = self.inorderTraversal(root.left)

            res.append(root.data)

            res = res + self.inorderTraversal(root.right)

        return res

 

root = Node(27)

root.insert(14)

root.insert(35)

root.insert(10)

root.insert(19)

root.insert(31)

root.insert(42)

print(root.inorderTraversal(root))