Python Program to Implement Binary Tree using Linked List

This is a Python program to implement a binary tree using a linked list.

Problem Description

The program creates a binary tree and presents a menu to the user to insert elements into the tree.

Problem Solution

1. Create a class BinaryTree with instance variables key, left and right.
2. Define methods set_root, insert_left, insert_right, inorder and search.
3. The method set_root takes a key as argument and sets the instance variable key equal to it.
4. The methods insert_left and insert_right insert a node as the left and right child respectively.
5. The method inorder displays the inorder traversal.
6. The method search returns a node with a specified key.

Program/Source Code

Here is the source code of a Python program to implement a binary tree using a linked list. The program output is shown below.

class BinaryTree:
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
 
    def set_root(self, key):
        self.key = key
 
    def inorder(self):
        if self.left is not None:
            self.left.inorder()
        print(self.key, end=' ')
        if self.right is not None:
            self.right.inorder()
 
    def insert_left(self, new_node):
        self.left = new_node
 
    def insert_right(self, new_node):
        self.right = new_node
 
    def search(self, key):
        if self.key == key:
            return self
        if self.left is not None:
            temp =  self.left.search(key)
            if temp is not None:
                return temp
        if self.right is not None:
            temp =  self.right.search(key)
            return temp
        return None
 
 
btree = None
 
print('Menu (this assumes no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('quit')
 
while True:
    print('inorder traversal of binary tree: ', end='')
    if btree is not None:
        btree.inorder()
    print()
 
    do = input('What would you like to do? ').split()
 
    operation = do[0].strip().lower()
    if operation == 'insert':
        data = int(do[1])
        new_node = BinaryTree(data)
        suboperation = do[2].strip().lower() 
        if suboperation == 'at':
                btree = new_node
        else:
            position = do[4].strip().lower()
            key = int(position)
            ref_node = None
            if btree is not None:
                ref_node = btree.search(key)
            if ref_node is None:
                print('No such key.')
                continue
            if suboperation == 'left':
                ref_node.insert_left(new_node)
            elif suboperation == 'right':
                ref_node.insert_right(new_node)
 
    elif operation == 'quit':
        break
Program Explanation

1. A variable is created to store the binary tree.
2. The user is presented with a menu to construct the binary tree.
3. The corresponding methods are called to perform each operation.

advertisement
Runtime Test Cases
Case 1:
Menu (this assumes no duplicate keys)
insert <data> at root
insert <data> left of <data>
insert <data> right of <data>
quit
inorder traversal of binary tree: 
What would you like to do? insert 3 at root
inorder traversal of binary tree: 3 
What would you like to do? insert 5 left of 3
inorder traversal of binary tree: 5 3 
What would you like to do? insert 2 right of 5
inorder traversal of binary tree: 5 2 3 
What would you like to do? insert 11 right of 3
inorder traversal of binary tree: 5 2 3 11 
What would you like to do? quit
 
Case 2:
Menu (this assumes no duplicate keys)
insert <data> at root
insert <data> left of <data>
insert <data> right of <data>
quit
inorder traversal of binary tree: 
What would you like to do? insert 1 at root
inorder traversal of binary tree: 1 
What would you like to do? insert 2 left of 1
inorder traversal of binary tree: 2 1 
What would you like to do? insert 3 right of 1
inorder traversal of binary tree: 2 1 3 
What would you like to do? insert 4 left of 2
inorder traversal of binary tree: 4 2 1 3 
What would you like to do? insert 5 right of 2
inorder traversal of binary tree: 4 2 5 1 3 
What would you like to do? insert 6 left of 3
inorder traversal of binary tree: 4 2 5 1 6 3 
What would you like to do? insert 7 right of 3
inorder traversal of binary tree: 4 2 5 1 6 3 7 
What would you like to do? quit

Sanfoundry Global Education & Learning Series – 1000 Python Programs.

If you wish to look at all Python Programming examples, go to 1000 Python Programs.

Free 30-Day Java Certification Bootcamp is Live. Join Now!

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.