(a) Write an algorithm to check whether two given binary trees are equal or not. (b) Write an algorithm to check whether a given binary tree is a proper binary tree or not. Give example.

(a) Algorithm to Check Whether Two Given Binary Trees are Equal

To determine if two binary trees are equal, we must ensure that they have the same structure and their corresponding nodes have the same values. Here is a step-by-step algorithm to check for equality:

Step 1: Define the Node Structure

First, define the structure of a tree node, which typically includes the value and pointers to the left and right children.

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

Step 2: Recursive Function to Compare Nodes

Create a recursive function that compares the nodes of the two trees.

def areTreesEqual(node1, node2):
    # Step 3: Check if both nodes are None
    if not node1 and not node2:
        return True

    # Step 4: Check if one of the nodes is None (trees are not equal)
    if not node1 or not node2:
        return False

    # Step 5: Compare the value of the nodes
    if node1.value != node2.value:
        return False

    # Step 6: Recursively compare the left and right subtrees
    return areTreesEqual(node1.left, node2.left) and areTreesEqual(node1.right, node2.right)

Step 3: Check if Both Nodes are None

If both nodes are None, it means we have reached the end of both trees simultaneously, and so far, they are equal.

Step 4: Check if One of the Nodes is None

If one node is None and the other is not, the trees are not equal because they have different structures.

Step 5: Compare the Value of the Nodes

If both nodes are not None, compare their values. If the values are not equal, the trees are not equal.

Step 6: Recursively Compare the Left and Right Subtrees

If the current nodes are equal, recursively call the function for the left children and the right children of both nodes.

Step 7: Return the Result

The function will return True if both trees are equal, otherwise False.

(b) Algorithm to Check Whether a Given Binary Tree is a Proper Binary Tree

A proper binary tree, also known as a full binary tree, is a tree in which every node has either 0 or 2 children. Here is how to check if a binary tree is a proper binary tree:

Step 1: Define the Node Structure

Use the same TreeNode class defined in part (a).

Step 2: Recursive Function to Check Proper Binary Tree

Create a recursive function that checks if a tree is a proper binary tree.

def isProperBinaryTree(node):
    # Step 3: Check if the node is None (empty tree is considered proper)
    if not node:
        return True

    # Step 4: Check if the node is a leaf node
    if not node.left and not node.right:
        return True

    # Step 5: Check if the node has both left and right children
    if node.left and node.right:
        # Step 6: Recursively check the left and right subtrees
        return isProperBinaryTree(node.left) and isProperBinaryTree(node.right)

    # Step 7: If the node has only one child, it's not a proper binary tree
    return False

Step 3: Check if the Node is None

An empty tree is considered a proper binary tree.

Step 4: Check if the Node is a Leaf Node

A leaf node (a node with no children) is always part of a proper binary tree.

Step 5: Check if the Node has Both Left and Right Children

A node with both left and right children satisfies the condition for being part of a proper binary tree.

Step 6: Recursively Check the Left and Right Subtrees

If the current node is not a leaf and has both children, recursively check if both the left and right subtrees are proper binary trees.

Step 7: If the Node has Only One Child

If a node has only one child, it does not satisfy the condition for a proper binary tree.

Step 8: Return the Result

The function will return True if the tree is a proper binary tree, otherwise False.

Example

Consider the following binary trees:

Tree A:       Tree B:       Tree C:
    1             1             1
   / \           / \           / 
  2   3         2   3         2
 / \ / \       /     \       / \
4  5 6  7     4       7     4   5

• Tree A and Tree B are equal and proper binary trees.
• Tree C is not a proper binary tree because the node with value 1 has only one child.

Using the algorithms provided, areTreesEqual(TreeA, TreeB) would return True, and isProperBinaryTree(TreeC) would return False.