Python program to check if leaf traversal of two Binary Trees is same

In this tutorial, we’ll learn how to check if leaf traversal of two Binary Trees is the same or not with the help of Python programming.

A binary tree is a hierarchical data structure in which each node has at most two children generally referred to as the left child and right child.

Explanation:

Given two binary trees

10                                                         5
/     \                                                   /     \
20      30                                             40     20
/             \                                                      /
40            50                                                 50

We can see that the leaf order traversal of the first binary tree is [40,50] and for the second binary tree is [40,50]. So, the leaf order traversal is the same for both binary trees.

Approach:

1. The idea is to make use of preorder traversal.
2. During each traversal, we check whether the left and right child of that node is None or not. If it’s None, then we append the info of that node to the list and call preorder traversal recursively.
3. After doing step 2 for both the binary trees, we’ll check whether the elements in the list for both the binary trees and equal and in the same order. If they satisfy the condition, then we’ll print “Same” otherwise we’ll print “Different”.

Implementation in Python

Below is given an example in Python programming:

class Node:
    
    def __init__(self,info):
        self.info=info
        self.left=None
        self.right=None

class BinaryTree:
    
    def __init__(self):
        self.root=None
        self.ans=[]

    def preorder(self,root):
        p=root
        if p is None:
            return
        
        if p.left is None and p.right is None:
            self.ans.append(p.info)
        
        self.preorder(p.left)
        self.preorder(p.right)

    def check(self,b2):
        if self.ans == b2.ans:
            return "Same"
        else:
            return "Different"

    def createtree1(self):
        self.root = Node(10)  
        self.root.left = Node(20)  
        self.root.right = Node(30)  
        self.root.left.left = Node(40)    
        self.root.right.right = Node(50)

    def createtree2(self):
        self.root =Node(5)  
        self.root.left = Node(40)  
        self.root.right = Node(20)    
        self.root.right.left = Node(50)

b1=BinaryTree()
b2=BinaryTree()

b1.createtree1()
b2.createtree2()

b1.preorder(b1.root)
b2.preorder(b2.root)

print(b1.check(b2))

Output:

Same

Recommended Posts:

• Preorder tree traversal in Python
• Boundary traversal of a tree in Python