Question

Write a python function comparing two binary trees and returns whethere they are same. Input two binary tress and output true or false. True= They are the same, False= They are not . Test the function .

Answer 1

BINARY TREE :- A binary tree is defined as a finite set of elements called as nodes such that

a. T is empty called the null tree

b. T contains a distinguished nodes F called the root of tree and the remaining nodes of the tree from an ordered pair of disjoint binary tree T1 and T2.

IDENTICAL TREE :- two trees are said to be identical when they have same data and same arrangement of data.

ALGORITHM FOR CHECKING WHETHER THE BINARY TREES ARE IDENTICAL OR NOT :-

1. Check for data for both trees. whether they are equal or not.

2. Turn to left of root.

3. Turn to right of root.

class TreeNode:

    def __init__(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right


# Recursive function

def same(x, y):

    # if both trees are empty,  it will return true

    if x is None and y is None:
        return True

    return (x and y) and (x.key == y.key) and \
           same(x.left, y.left) and same(x.right, y.right)


if __name__ == '__main__':

    # Nodes of first binary tree

    x = TreeNode(6)
    x.left = TreeNode(2)
    x.right = TreeNode(8)
    x.left.left = TreeNode(3)
    x.left.right = TreeNode(5)

    # Nodes of second binary tree

    y = TreeNode(6)
    y.left = TreeNode(2)
    y.right = TreeNode(8)
    y.left.left = TreeNode(3)
    y.left.right = TreeNode(5)

    if same(x, y):
        print("True = they are same")
    else:
        print("False = they are not ")

OUTPUT : -
True = they are same

Process finished with exit code 0

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------THANK YOU ----------------------------------------------------------------------------------