Python Program to Construct Binary Tree from Postorder and Inorder

This is a Python program to build a binary tree with in-order and post-order traversals as input.

Problem Description

The program builds a binary tree from their in-order and post-order traversals.

Problem Solution

1. Create a class BinaryTree with instance variables key, left and right.
2. Define methods set_root, inorder, and postorder.
3. The method set_root takes a key as argument and sets the instance variable key equal to it.
4. The method inorder displays an in-order traversal of the binary tree.
5. The method postorder displays a post-order traversal of the binary tree.
6. Define the function construct_btree which takes two lists postord and inord as arguments.
7. The function construct_btree returns a binary tree that has post-order traversal postord and in-order traversal inord.

Program/Source Code

Here is the source code of a Python program to build a binary tree with in-order and post-order traversals as input. 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 postorder(self):
        if self.left is not None:
            self.left.postorder()
        if self.right is not None:
            self.right.postorder()
        print(self.key, end=' ')
 
 
def construct_btree(postord, inord):
    if postord == [] or inord == []:
        return None
    key = postord[-1]
    node = BinaryTree(key)
    index = inord.index(key)
    node.left = construct_btree(postord[:index], inord[:index])
    node.right = construct_btree(postord[index:-1], inord[index + 1:])
    return node
 
 
postord = input('Input post-order traversal: ').split()
postord = [int(x) for x in postord]
inord = input('Input in-order traversal: ').split()
inord = [int(x) for x in inord]
 
btree = construct_btree(postord, inord)
print('Binary tree constructed.')
print('Verifying:')
print('Post-order traversal: ', end='')
btree.postorder()
print()
print('In-order traversal: ', end='')
btree.inorder()
print()
Program Explanation

1. The user is prompted to enter the post-order and in-order traversals for the binary tree.
2. The function construct_btree is called to build the binary tree.
3. The constructed binary tree’s post-order and in-order traversals are displayed for verification.

advertisement
advertisement
Runtime Test Cases
Case 1:
Input post-order traversal: 4 5 2 8 6 7 3 1
Input in-order traversal: 4 2 5 1 6 8 3 7
Binary tree constructed.
Verifying:
Post-order traversal: 4 5 2 8 6 7 3 1 
In-order traversal: 4 2 5 1 6 8 3 7 
 
Case 2:
Input post-order traversal: 2 1 3
Input in-order traversal: 2 3 1
Binary tree constructed.
Verifying:
Post-order traversal: 2 1 3 
In-order traversal: 2 3 1

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

If you find any mistake above, kindly email to [email protected]

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
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.