Check inorder subsequence and edit tree minimally
Overview
This question evaluates proficiency in tree traversal and subsequence matching under tight resource constraints, testing skills in streaming inorder traversal, memory-efficient algorithms, and reasoning about subsequences within binary trees; it falls under the Coding & Algorithms domain and requires practical implementation ability combined with conceptual algorithmic reasoning. The follow-up on minimally editing the tree and computing a minimum-cost edit sequence assesses understanding of edit-distance-like reasoning on tree structures, handling edge cases (empty target, duplicates, longer target) and analyzing time/space complexity, which is commonly asked to evaluate optimization, problem decomposition, and correctness under constraints.
Given a binary tree whose nodes store integers and an array target, determine whether target is a subsequence of the tree's inorder traversal (elements must appear in the same relative order but not necessarily contiguously). Aim for O(n) time and O(
- auxiliary space by streaming the traversal without storing it. Follow-ups:
- Modify the tree so that its inorder traversal contains target as a subsequence. Allowed operations: overwrite the value of any existing node or insert a new node anywhere in the tree; each operation has cost 1.
- Compute the minimum number of operations required and output that minimum and one valid set of edits (or a modified tree) achieving it. Discuss edge cases (e.g., empty target, duplicates, target longer than traversal) and state time/space complexity for each part.