Katkat
Back

Count changed nodes between two menu trees

DoorDashSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests recursive tree traversal and hierarchical diffing strategies to identify structural and content changes between two versions of a menu tree.

Problem Statement

You are given two versions of a restaurant menu represented as N-ary trees. Each node in the tree has a unique id, a value (e.g., price or item name), and a list of children.

When comparing the old_tree to the new_tree, you need to count the total number of "changed" nodes. A node is considered changed if:

  1. It exists in both trees, but its value has been modified.
  2. It exists in the new_tree but not the old_tree (Addition).
  3. It exists in the old_tree but not the new_tree (Removal).

Two nodes are considered the same if they share the same id. Assume that if an id is present in both trees, its position in the hierarchy remains the same.

Implement the function: count_changed_nodes(root1, root2)

Constraints

  • id is unique across the entire tree.
  • Number of nodes N is up to 10^5.
  • The tree is not necessarily binary.

Examples

Example 1:

  • old: {id: 1, val: "Pizza", children: []}
  • new: {id: 1, val: "Pepperoni Pizza", children: []}
  • Result: 1 (The node with id 1 changed value).

Example 2:

  • old: {id: 1, children: [{id: 2, val: "Coke"}]}
  • new: {id: 1, children: []}
  • Result: 1 (Node 2 was removed).

Edge Cases

  • One or both trees are empty (None/null).
  • Deeply nested trees requiring recursion depth management.

Hints

Hint 1

Use a hash map or dictionary to store all node values from the old tree, keyed by ID, to allow O(1) lookup during the second traversal.

Hint 2

Perform a post-order traversal on the new tree to compare existing nodes and identify additions, while simultaneously tracking which nodes from the old tree were 'visited' to identify removals.

Hint 3

The total count is the sum of nodes with mismatched values, nodes found only in the new tree, and nodes found only in the old tree that were never visited.

Follow-up questions

  • How would your approach change if nodes could move to different parents (i.e., the structure changes, not just the content)?
  • How would you optimize the solution if the tree is too large to fit entirely in memory?
  • If the 'value' field is a complex object (e.g., a dictionary of attributes), how do you efficiently check for partial equality?