Count changed nodes in N-ary trees
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Given two N-ary trees (old and new versions) where each node has a key (string), value (int), and list of children, compute how many nodes are considered "changed" in the new tree. A node counts as changed if it is:
deleted (present in old, absent in new),
added (absent in old, present in new),
has a different value for the same key, or
has the same key/value but a different parent compared with the old tree.
Design an efficient algorithm and explain its time- and space-complexity.
Quick Answer: This question evaluates understanding of N-ary tree data structures, structural comparison of hierarchical versions, and the ability to reason about time and space complexity when detecting added, deleted, value-changed, or reparented nodes.
You are given two rooted N-ary trees representing old and new versions. Each node has: key (unique string), value (integer), and children (list of child keys). Keys identify the same logical node across versions. A node is considered changed if it is present in old but absent in new (deleted), present in new but absent in old (added), present in both but its value differs, or present in both with the same value but its parent key differs (treat the root's parent as None). Implement count_changed_nodes(old_tree, new_tree) that returns the total number of changed nodes.
Input: old_tree and new_tree are lists of node objects: {"key": string, "value": int, "children": [string, ...]}. Each children key appears as some node's key in the same list, and the edges form a valid rooted tree (no cycles; each node except the root has exactly one parent). Either list may be empty.
Constraints
- 0 <= len(old_tree), len(new_tree) <= 200000
- Sum of lengths of all children lists in each tree <= 200000
- Keys are unique within each tree and identify nodes across versions
- Values are 32-bit signed integers
- Each input describes a valid rooted tree (acyclic, each non-root has exactly one parent)
Hints
- Map each key to its value and its parent key (None for the root) in both trees.
- Build parent maps by scanning children lists; you do not need to traverse the trees.
- Compare over the union of keys from both trees to count additions, deletions, value changes, and parent (move) changes.
- Treat the root's parent as None when comparing parent keys.