Katkat
Back

Compute Differences Between Catalog Trees

DoorDashSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates proficiency in tree algorithms and hierarchical data comparison, including simultaneous traversal, subtree sizing, key-based node identity, and time/space complexity reasoning, and is commonly asked to assess algorithmic problem-solving and trade-off analysis when comparing structured datasets.

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.