Compute Differences Between Catalog Trees

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: ( 1) nodes that exist only in the left tree or only in the right tree count toward the total; ( 2) 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; ( 3) 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.