This is a Python program to build a binary tree with in-order and post-order traversals as input.
The program builds a binary tree from their in-order and post-order traversals.
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.
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()
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.
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.
- Practice Programming MCQs
- Check Python Books
- Check Information Technology Books
- Apply for Python Internship
- Apply for Programming Internship
