Check if Two Trees are Identical 🎯

Welcome to another engaging lesson at CodeYourCraft! Today, we're going to dive into the fascinating world of Data Structures and Algorithms. Specifically, we're going to learn about tree comparison and determine if two trees are identical. Let's get started!

What are Trees? 📝

Trees are a type of data structure used to represent hierarchical or nested relationships. They consist of nodes, where each node has a value and zero or more children. We'll delve deeper into trees in the future, but for now, let's focus on understanding how to compare them.

Comparing Trees 💡

Comparing trees can be a complex task, but it's essential to understand when working with various data structures. In this lesson, we'll create a function that checks if two trees are identical.

Identical Trees ✅

Two trees are said to be identical if they have the same structure and the same values for their nodes. Here's an example of two identical trees:

  1
 / \
2   3

Both trees above have the same structure and the same values, making them identical.

Function to Check Identical Trees 💡

Now let's create a function in Python to check if two trees are identical:

python

def are_identical_trees(tree1, tree2):
    if not tree1 and not tree2:
        return True
    if not tree1 or not tree2:
        return False
    if tree1.val != tree2.val:
        return False
    return are_identical_trees(tree1.left, tree2.left) and are_identical_trees(tree1.right, tree2.right)

In this function, we first check if both trees are empty, in which case they are identical. If either tree is not empty, we check if both trees have the same value for the root node. If they do, we recursively call the function on the left and right children of each tree.

Practice Time 🎯

Now it's time for you to practice! Here's a quiz to help you reinforce your understanding of identical trees:

Stay tuned for more lessons on Data Structures and Algorithms! 📝

Complete Code Examples 💡

Let's take a look at a complete example of using the are_identical_trees function:

python

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

def are_identical_trees(tree1, tree2):
    # Your code here
    pass

# Example usage
tree1 = TreeNode(1)
tree1.left = TreeNode(2)
tree1.right = TreeNode(3)

tree2 = TreeNode(1)
tree2.left = TreeNode(2)
tree2.right = TreeNode(3)

print(are_identical_trees(tree1, tree2))  # Should print True

tree2.right = TreeNode(4)

print(are_identical_trees(tree1, tree2))  # Should print False

In this example, we define a TreeNode class and implement the are_identical_trees function. We then create two identical trees and call the function to check if they're identical. Finally, we modify the second tree to make it non-identical and observe the function's behavior.

We hope you enjoyed this lesson on comparing trees! Stay tuned for more in-depth lessons on Data Structures and Algorithms at CodeYourCraft. 🎯