C Language Algorithm: Identical Trees

Today's algorithm problem is to solve the "Identical Trees" algorithm using C language. Below are my algorithm ideas and implementation. Let's take a look.
Algorithm Problem
Given two binary trees, determine if they are identical. They are considered identical if they have the same structure and their node values are the same.
Algorithm Idea
The method to solve the identical trees problem is to use recursion. Here are the detailed steps of the algorithm:
Define a recursive function isSameTree that takes two binary trees p and q as parameters.
In the isSameTree function, first check if both root nodes of the two trees are null. If both are null, return true, since empty trees are considered identical.
Otherwise, check if the values of the root nodes of the two trees are equal. If they are not equal, return false.
Recursively call the isSameTree function to compare the left and right subtrees of the two trees. Only if both subtrees are identical, the entire tree is considered identical.
Finally, return the result of the recursive calls.


👇 Click to claim 👇
👉 C Language Knowledge Resource Collection

Code Implementation

Here is an example code implementation of the "Identical Trees" algorithm in C:
#include <stdio.h>
#include <stdbool.h>
// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // If both root nodes of the two trees are null, they are considered identical.
    if (p == NULL && q == NULL) {
        return true;
    }
    // If one of the root nodes is null and the other is not, they are not identical.
    if (p == NULL || q == NULL) {
        return false;
    }
    // If the values of the root nodes of the two trees are not equal, they are not identical.
    if (p->val != q->val) {
        return false;
    }
    // Recursively compare the left and right subtrees of the two trees.
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
Algorithm Analysis
The time complexity of the recursive algorithm for the identical trees problem is O(n), where n is the number of nodes in the binary tree, because we need to compare the value of each node. The space complexity is O(h), where h is the height of the binary tree, because the depth of the recursive call stack depends on the height of the tree.

Example and Testing
Let's use an example to test our identical trees program. Suppose we have the following two binary trees:
First Tree:
   1  
  / \  
 2   3
Second Tree:
   1  
  / \  
 2   3
Running the above code, we will get the following output:
The two trees are identical.
This indicates that we have successfully determined that the two binary trees are identical.
Summary
Determining whether two binary trees are identical is a common tree traversal and comparison problem. By using a recursive method, we can efficiently solve this problem, comparing the node values of the two trees layer by layer. In this article, we have implemented an algorithm in C language to determine whether two binary trees are identical. By discussing the algorithm idea, code implementation, algorithm analysis, and examples and testing in detail, we hope readers can understand and apply this concept to solve similar problems. This problem has wide applications in tree comparison and operations, and it is a useful problem for programmers interested in algorithms and data structures.

 Recommended Hot

• CLion Tutorial – Creating a Directory in CLion

• C Language Algorithm – “Recover Binary Search Tree” Algorithm Problem

• C++ Tutorial – Detailed Explanation of the Differences Between C++ and C#