#711 List the Patches Between Two Trees

Implement a tiny virtual DOM diff. A node is { type, props, children }. Name each node by its path: the root is "0", and child i of a node at path p is at p + "." + i.

Write diffTrees(oldTree, newTree) that compares the trees starting at the roots with these rules, and returns the patches in the order they are produced:

• No old node: ["insert", path, newType]. No new node: ["remove", path]. Different type: ["replace", path, newType]. In these three cases, the children are not compared.

• Same type: first, for each prop key whose value differs (!==), add ["prop", path, key, newValue], using null when the new node doesn't have the key. Check the old node's keys in their order, then keys only the new node has, in their order. Then compare children pair by pair by position, from 0 up to the longer list's length.

Either tree may be null. Prop values are strings, numbers, or booleans.

Input: oldTree = {"type":"div","props":{"class":"card"},"children":[{"type":"h2","props":{"id":"t"},"children":[]},{"type":"p","props":{},"children":[]}]}, newTree = {"type":"div","props":{"class":"card active"},"children":[{"type":"h2","props":{"id":"t"},"children":[]},{"type":"span","props":{},"children":[]},{"type":"button","props":{"type":"submit"},"children":[]}]}
Output: [["prop","0","class","card active"],["replace","0.1","span"],["insert","0.2","button"]]

Input: oldTree = {"type":"ul","props":{},"children":[{"type":"li","props":{},"children":[]},{"type":"li","props":{},"children":[]},{"type":"li","props":{},"children":[]}]}, newTree = {"type":"ul","props":{},"children":[{"type":"li","props":{},"children":[]}]}
Output: [["remove","0.1"],["remove","0.2"]]

Constraints

• Each tree has 0 to 10^3 nodes.