💡 Problem Formulation: Given two binary trees, we aim to determine if they are identical in both structure and content. Identical trees must have the same number of nodes with identical positions and corresponding nodes must contain the same value. For instance, if Tree A and Tree B both have a root node with the value ‘3’ and left child node ‘4’, they are identical only if the entire structure and node values of both trees match exactly.
Method 1: Recursive Traversal
The recursive traversal method involves comparing nodes recursively, checking each node’s value simultaneously in both trees, and ensuring both left and right subtrees are also identical. This function should return true if both trees are the same or false otherwise. The function is called recursively for left and right subtrees.
Here’s an example:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_same_tree(p, q):
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
# Example Trees
tree1 = TreeNode(1, TreeNode(2), TreeNode(3))
tree2 = TreeNode(1, TreeNode(2), TreeNode(3))
print(is_same_tree(tree1, tree2))Output:
True
This code snippet defines a binary tree using the TreeNode class and checks if two binary trees (tree1 and tree2) are identical using the is_same_tree() function. It performs a depth-first traversal, comparing nodes from both trees and ensuring that the structures and values are the same at each step.
Method 2: Iterative Traversal
Iterative traversal is similar to recursive traversal, but uses a stack to compare nodes without the function call overhead. We traverse both trees in parallel and compare nodes as they’re visited. This can be done using any traversal order, but here we’ll demonstrate pre-order traversal.
Here’s an example:
def is_same_tree_iterative(p, q):
stack = [(p, q)]
while stack:
node1, node2 = stack.pop()
if not node1 and not node2:
continue
if not node1 or not node2 or node1.val != node2.val:
return False
stack.append((node1.right, node2.right))
stack.append((node1.left, node2.left))
return True
# Assume TreeNode class and example trees as defined in Method 1
print(is_same_tree_iterative(tree1, tree2))Output:
True
The code snippet here implements an iterative version of the is_same_tree() function called is_same_tree_iterative(). It uses a stack to iteratively traverse both trees and perform node comparisons, maintaining structure and value integrity checks.
Method 3: Level-Order Traversal
This approach uses level-order traversal to compare nodes’ values at each level of both trees using a queue. It is a breadth-first search strategy that visits each level of the tree before proceeding to the next one. This method is intuitive and closely resembles how one might visually compare two trees.
Here’s an example:
from collections import deque
def is_same_tree_level_order(p, q):
queue = deque([(p, q)])
while queue:
for _ in range(len(queue)):
node1, node2 = queue.popleft()
if not node1 and not node2:
continue
if not node1 or not node2 or node1.val != node2.val:
return False
queue.append((node1.left, node2.left))
queue.append((node1.right, node2.right))
return True
# Assume TreeNode class and example trees as defined in Method 1
print(is_same_tree_level_order(tree1, tree2))Output:
True
The code snippet illustrates is_same_tree_level_order(), a function that uses level-order traversal to compare trees. Nodes are visited level by level, and their existence and values are compared using a queue, with the process continuing as long as the queue isn’t empty.
Method 4: String Serialization
In this method, we serialize both trees to a string representation and then compare these strings. Serialization involves a systematic encoding of tree nodes and null markers to fully represent the tree’s structure and values. We can use pre-order traversal for serialization.
Here’s an example:
def serialize(root):
return "X" if not root else f"{root.val} {serialize(root.left)} {serialize(root.right)}"
# Assume TreeNode class and example trees as defined in Method 1
print(serialize(tree1) == serialize(tree2))Output:
True
The code snippet creates a serialization of each tree using the serialize() function, which transforms the tree into a string using pre-order traversal. By comparing the resulting strings for both trees, we can determine if they are identical.
Bonus One-Liner Method 5: Using Equality Operator with Nested Tuples
A Pythonic one-liner can achieve the comparison task by converting the tree structure into nested tuples and then using the equality operator to compare them. This method leverages the tuple data structure’s innate ability to be compared for equality, which includes recursive checks for nested structures.
Here’s an example:
def tupleize(root):
return (root.val, tupleize(root.left), tupleize(root.right)) if root else None
# Assume TreeNode class and example trees as defined in Method 1
print(tupleize(tree1) == tupleize(tree2))Output:
True
This code snippet uses the tupleize() function to convert each tree into a nested tuple reflecting its structure and value. The comparison is then a simple check using the ‘==’ operator.
Summary/Discussion
- Method 1: Recursive Traversal. Uses simple recursion for depth-first search. Strengths: easy to understand and implement. Weaknesses: possible stack overflow for deep trees.
- Method 2: Iterative Traversal. Uses explicit stack to avoid recursion overhead. Strengths: better control over traversal, no recursion stack limit. Weaknesses: slightly more complex implementation.
- Method 3: Level-Order Traversal. Uses a queue for breadth-first search. Strengths: intuitive comparison level by level. Weaknesses: requires additional memory proportional to the width of the tree.
- Method 4: String Serialization. Compares serialized string representations of trees. Strengths: simple string comparison, good for debugging. Weaknesses: additional overhead of serialization and more memory usage.
- Bonus Method 5: Using Equality Operator with Nested Tuples. Pythonic, concise one-liner with implicit recursion. Strengths: elegant and efficient. Weaknesses: less readable, requires understanding of tuple comparison.