What is the time and space complexity of Find Node in DOM Trees?

Time complexity: O(d) where d is the tree depth. Space complexity: O(d) for the path array.

Find Node in DOM Trees

Med

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Find Node in DOM Trees

Approach

Walk from the target node up to the root in Tree A, recording the child index at each level to build a path. Then follow that same index path from the root of Tree B downward to locate the corresponding node.

Complexity Analysis

Time: O(d) where d is the tree depth
Space: O(d) for the path array

Pattern

Tree Path Traversal

Why It Works

Since both trees have identical structure, a node's position is uniquely identified by its index path from the root. Replaying that path in the clone tree lands on the structurally equivalent node.

Updated Mar 2026