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 Approachesclick to switch
FIG. SAME TREE● INTERACTIVE
visualization loads as you reach it
Time
O(min(m,n))
  • m = size of p, n = size of q. dfs(a, b) recurses on both children together, so as soon as either side runs out of nodes the mismatch is caught and recursion stops - at most min(m,n) node pairs are ever visited.
Space
O(min(m,n))
  • The recursion call stack can only go as deep as the smaller tree allows before a node is missing on one side, so it holds at most min(m,n) frames.
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 Approachesclick to switch
FIG. SYMMETRIC TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits every node exactly once across the mirrored recursion.
Space
O(h)
  • The recursion call stack grows with tree height h.
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)

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 Approachesclick to switch
FIG. FIND CORRESPONDING NODE RECURSIVE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits up to all n nodes of original in the worst case, when target is the last node reached.
Space
O(h)
  • The recursion call stack grows with the tree's height h.
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 Approachesclick to switch
FIG. LEAF SIMILAR TREES● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the total number of nodes across both trees - the recursion in recursion visits every node of root1 and root2 exactly once.
Space
O(n)
  • list(recursion(root1)) and list(recursion(root2)) materialize every leaf value before the comparison, up to O(n) leaves combined.
  • The recursion stack only reaches depth h (the taller tree's height), which is dominated by the materialized leaf lists.
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))