Write an algorithm to check whether two given binary trees are equal or not.

To check whether two given binary trees are equal or not, we can use a recursive algorithm that compares the nodes of both trees simultaneously. Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Here's a step-by-step algorithm to determine if two binary trees are equal:

Algorithm: Check Equality of Two Binary Trees

Step 1: Check for Base Cases

• If both trees are empty (i.e., both root nodes are NULL), then they are equal. Return true.
• If one tree is empty and the other is not (i.e., one root is NULL and the other is not), then they are not equal. Return false.

Step 2: Compare Current Nodes

• If the value of the current nodes of both trees is not the same, return false.

Step 3: Recurse for Subtrees

• Recursively check the equality of the left subtrees.
• Recursively check the equality of the right subtrees.

Step 4: Combine Results

• If the values of the current nodes are the same and the recursive checks for both left and right subtrees return true, then the trees are equal. Return true.
• Otherwise, return false.

Pseudocode

FUNCTION AreTreesEqual(node1, node2)
    IF node1 IS NULL AND node2 IS NULL
        RETURN true
    END IF
    IF node1 IS NULL OR node2 IS NULL
        RETURN false
    END IF
    IF node1.value != node2.value
        RETURN false
    END IF
    RETURN AreTreesEqual(node1.left, node2.left) AND AreTreesEqual(node1.right, node2.right)
END FUNCTION

Example

Let's consider two binary trees to illustrate the algorithm:

Tree 1:       Tree 2:
    1             1
   / \           / \
  2   3         2   3

• Both trees have the same root value (1).
• The left child of both trees is the same (2).
• The right child of both trees is the same (3).
• There are no further nodes to compare.

Using the algorithm, we would start at the root of both trees and compare their values. Since they are the same, we would then recursively compare the left and right subtrees. Since all comparisons return true, the algorithm would ultimately return true, indicating that the trees are equal.

Implementation in Python

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

def are_trees_equal(node1, node2):
    if not node1 and not node2:
        return True
    if not node1 or not node2:
        return False
    if node1.value != node2.value:
        return False
    return are_trees_equal(node1.left, node2.left) and are_trees_equal(node1.right, node2.right)

# Example usage:
# Constructing Tree 1
node1 = TreeNode(1)
node1.left = TreeNode(2)
node1.right = TreeNode(3)

# Constructing Tree 2
node2 = TreeNode(1)
node2.left = TreeNode(2)
node2.right = TreeNode(3)

# Check if Tree 1 and Tree 2 are equal
print(are_trees_equal(node1, node2))  # Output: True

This Python code defines a TreeNode class for the nodes of the binary tree and implements the are_trees_equal function following the algorithm described above. The example usage constructs two identical trees and checks if they are equal, which in this case, they are.