You are given two rooted catalog trees. Each node has a unique string key among its siblings and an associated value. Compare the two trees and return the total number of differing nodes under these rules:
(
-
nodes that exist only in the left tree or only in the right tree count toward the total;
(
-
if two nodes share the same path of keys but their values differ, treat the entire subtree at that node as 'delete + recreate' and count all nodes in the left subtree as deletions plus all nodes in the right subtree as creations;
(
-
child order is irrelevant and keys define identity. Design an efficient algorithm that traverses both trees simultaneously (e.g., a primary DFS with an auxiliary subtree-size computation) to compute the count. Analyze time and space complexity, describe edge cases (empty trees, duplicate keys, extremely unbalanced trees), and provide pseudocode or code.