Tejav
#1379

Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Easy
TreeDepth-First SearchBreadth-First SearchBinary TreeDepth-First SearchRecursion
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(h)
💡

Intuition

Time O(n)Space O(h)

In the optimal approach, we can use a single traversal of the cloned tree while checking against the target node. This way, we avoid redundant searches.

⚙️

Algorithm

3 steps
  1. 1Step 1: Perform a depth-first search (DFS) on the cloned tree.
  2. 2Step 2: If the current node matches the target node, return the current node.
  3. 3Step 3: Continue the search in the left and right subtrees.
solution.py9 lines
1def getTargetCopy(original, cloned, target):
2    def dfs(node):
3        if not node:
4            return None
5        if node.val == target.val:
6            return node
7        left = dfs(node.left)
8        return left if left else dfs(node.right)
9    return dfs(cloned)
ℹ

Complexity note: The time complexity is O(n) because we traverse each node in the cloned tree once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

  • 1Both trees are structurally identical, allowing us to find the target in the cloned tree by matching values.
  • 2Using DFS allows us to efficiently search without unnecessary traversals.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.