Quick Overview

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.

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.

Overview: 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

  1. Map each key to its value and its parent key (None for the root) in both trees.
  2. Build parent maps by scanning children lists; you do not need to traverse the trees.
  3. Compare over the union of keys from both trees to count additions, deletions, value changes, and parent (move) changes.
  4. Treat the root's parent as None when comparing parent keys.

Loading coding console...

Show the approach

Approach

Build two hash maps per tree: key->value and key->parent_key (parent of root is None). The parent maps are derived by scanning each node's children and assigning the child's parent. Then iterate over the union of keys from both trees. For each key: if it appears in only one tree, count it as changed (addition or deletion). If it appears in both, compare values; if they differ, count as changed. Otherwise, compare parent keys; if they differ (including None vs non-None), count as changed. Sum these to get the total number of changed nodes.

Time complexity:
O(n + m)
Space complexity:
O(n + m)