Count changed nodes in N-ary trees

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.

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.

|Home/Coding & Algorithms/DoorDash
DoorDash logo
DoorDash
Jul 29, 2025, 8:05 AM
mediumSoftware EngineerTechnical ScreenCoding & Algorithms
13
0
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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...