Skip to main content

Two Trees

100. Same Tree​

Easy·

Two binary trees are considered the same if they are structurally identical, and the nodes have the same values in the same positions.

2 Approaches
FIG. SAME TREE● INTERACTIVE
visualization loads as you reach it
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
def dfs(a, b):
if not a and not b:
return True
if not a or not b:
return False
if a.val != b.val:
return False
return dfs(a.left, b.left) and dfs(a.right, b.right)
 
return dfs(p, q)

101. Symmetric Tree​

Easy·

A tree is symmetric if the left subtree is a mirror reflection of the right subtree. This means comparing left.left with right.right and left.right with right.left.

2 Approaches
FIG. SYMMETRIC TREE● INTERACTIVE
visualization loads as you reach it
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def dfs(left, right):
if not right and not left:
return True
if not right or not left:
return False
if left.val != right.val:
return False
return dfs(left.left, right.right) and dfs(left.right, right.left)
 
return dfs(root, root)

572. Subtree of Another Tree​

Easy·

subRoot is a subtree of root when some node of root, taken together with everything below it, is identical to subRoot.

FIG. SUBTREE OF ANOTHER TREE● INTERACTIVE
visualization loads as you reach it
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: TreeNode | None, q: TreeNode | None) -> bool:
def rec(left, right):
if not left and not right:
return True
elif not left or not right:
return False
x = rec(left.left, right.left)
y = rec(left.right, right.right)
return x and y and left.val == right.val
 
return rec(p, q)
 
def isSubtree(self, root: TreeNode | None, subRoot: TreeNode | None) -> bool:
def rec(node):
if not node:
return False
if node.val == subRoot.val:
if self.isSameTree(node, subRoot):
return True
 
left = rec(node.left) if node.left else None
right = rec(node.right) if node.right else None
return left or right
 
return rec(root)

1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree​

Easy·

Given two binary trees original and cloned, and a reference to a target node in the original tree, find the corresponding node in the cloned tree. The cloned tree is a deep copy of the original tree.

3 Approaches
FIG. FIND CORRESPONDING NODE RECURSIVE● INTERACTIVE
visualization loads as you reach it
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
def dfs(a, b):
if a and b:
if a == target:
return b
left_result = dfs(a.left, b.left)
right_result = dfs(a.right, b.right)
return left_result or right_result
 
return dfs(original, cloned)

872. Leaf-Similar Trees​

Easy·

Two trees are leaf-similar if their leaf values, read left to right, form the same sequence. Generate each tree's leaf sequence with a DFS and compare. The recursive variants use a generator (yield) so leaves stream out in order; the O(1)-space variants compare lazily with zip_longest instead of materializing both lists.

4 Approaches
FIG. LEAF SIMILAR TREES● INTERACTIVE
visualization loads as you reach it
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def recursion(node):
if not node:
return
if not node.left and not node.right:
yield node.val
yield from recursion(node.left)
yield from recursion(node.right)
 
return list(recursion(root1)) == list(recursion(root2))