Katkat
Back

Count changed nodes in N-ary trees

DoorDashSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.