Count changed nodes between two menu trees
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You maintain a merchant menu as a rooted tree. Each node represents a menu item/category and has:
- `key` (string, unique among siblings)
- `value` (integer)
- `children` (0..k child nodes)
When a merchant sends a new menu tree, you want to count how many nodes have **changed** compared to the existing menu.
A node is considered **changed** if any of the following is true:
1. **Removed (deactivated):** A node exists in the old tree but does not exist in the new tree **at the same position** (i.e., under the same parent). Count every node in the removed subtree as changed.
2. **Added:** A node exists in the new tree but does not exist in the old tree **at the same position**. Count every node in the added subtree as changed.
3. **Updated value:** A node exists in both trees at the same position (same parent and same `key`), but its `value` differs.
Important: If a node with the same `key` appears under a **different parent** in the new tree, treat this as **removal of the old node (and its subtree)** plus **addition of the new node (and its subtree)**.
### Task
Given the roots of the old and new trees, return the number of changed nodes.
### Example 1
Old tree:
- a(1)
- b(2)
- d(4)
- e(5)
- c(3)
- f(6)
New tree:
- a(1)
- c(3)
- f(66)
Output: `4`
Explanation: `b`, `d`, `e` are removed (3 changes) and `f` value changes from 6 to 66 (1 change).
### Example 2
Old tree:
- a(1)
- b(2)
- d(4)
- e(5)
- c(3)
- g(7)
New tree:
- a(1)
- b(2)
- e(5)
- d(4)
- f(6)
- h(8)
- g(7)
Output: `5`
Explanation: `f` is added (1). Subtree rooted at `c` is removed (`c` and its child `g`: 2). Subtree rooted at `h` is added (`h` and its child `g`: 2). Total = 1 + 2 + 2 = 5.
### Constraints (you may assume)
- Total number of nodes across both trees up to `2 * 10^5`.
- Children order does not matter.
- `key` is unique among siblings (so children can be matched by `key` under the same parent).
Design an algorithm to compute the count efficiently.
Quick Answer: This question evaluates algorithmic problem-solving with tree data structures, testing competencies in hierarchical diffing, node matching by sibling keys, subtree addition/removal counting, and handling value updates while respecting performance constraints.
You are given two rooted menu trees: an old menu and a new menu. Each node is represented as `(key, value, children)`, where `key` is a string, `value` is an integer, and `children` is a list of child nodes. An empty tree is represented by `None`.
Count how many nodes have changed between the two trees.
A node is considered changed if:
1. It exists in the old tree but not in the new tree at the same position. In that case, every node in the removed subtree counts as changed.
2. It exists in the new tree but not in the old tree at the same position. In that case, every node in the added subtree counts as changed.
3. It exists in both trees at the same position (same parent and same `key`), but its `value` is different. Then only that node counts as changed for the value update.
Important rules:
- Children order does not matter.
- Siblings have unique `key` values, so children under the same parent should be matched by `key`.
- If the same `key` appears under a different parent in the new tree, treat it as a removal from the old location plus an addition at the new location.
- At the root, nodes match only if their root `key` is the same.
Return the total number of changed nodes efficiently.