PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick 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.

  • Medium
  • Airbnb
  • Coding & Algorithms
  • Software Engineer

Check inorder subsequence and edit tree minimally

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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( 1) auxiliary space by streaming the traversal without storing it. Follow-ups: 1) 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. 2) 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.

Quick Answer: 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.

Part 1: Check Whether Target Is an Inorder Subsequence

You are given a binary tree whose nodes store integers and an array target. Determine whether target is a subsequence of the tree's inorder traversal. The traversal must be streamed: do not build the full inorder list first. In this problem, a tree node is encoded as a nested Python dictionary: {'val': int, 'left': node_or_None, 'right': node_or_None}. Return True if all values of target appear in inorder in the same relative order, and False otherwise.

Constraints

  • 0 <= number of nodes <= 100000
  • 0 <= len(target) <= 100000
  • -10^9 <= node values, target values <= 10^9
  • Duplicate values are allowed

Examples

Input: ({'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}, [1, 3])

Expected Output: True

Explanation: The inorder traversal is [1, 2, 3], and [1, 3] is a subsequence.

Input: ({'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}, [3, 1])

Expected Output: False

Explanation: The values appear in the wrong relative order.

Input: ({'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': {'val': 2, 'left': None, 'right': None}}, [2, 2])

Expected Output: True

Explanation: The inorder traversal is [1, 2, 2], so the duplicate target is present as a subsequence.

Input: (None, [])

Expected Output: True

Explanation: The empty array is a subsequence of any traversal, including an empty one.

Input: (None, [1])

Expected Output: False

Explanation: A non-empty target cannot be a subsequence of an empty traversal.

Hints

  1. Keep one pointer into target. Advance it only when the current inorder value matches target[pointer].
  2. Morris inorder traversal lets you stream inorder values using O(1) auxiliary space by temporarily threading the tree.

Part 2: Deterministically Modify the Tree So Target Appears in Inorder

You are given a binary tree of integers and an array target. Return a modified tree whose inorder traversal contains target as a subsequence, following this exact deterministic strategy: (1) scan the existing tree in inorder; for the k-th visited existing node, if k < len(target), overwrite that node's value with target[k]; otherwise leave it unchanged; (2) after the inorder scan, if target still has remaining values, append them as a chain of new right children after the original rightmost node; (3) if the original tree is empty, create a pure right-child chain containing all target values. Use the same nested-dict tree format as Part 1.

Constraints

  • 0 <= number of nodes <= 100000
  • 0 <= len(target) <= 100000
  • -10^9 <= node values, target values <= 10^9
  • Duplicate values are allowed

Examples

Input: ({'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}, [4, 5])

Expected Output: {'val': 5, 'left': {'val': 4, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}

Explanation: The first two inorder nodes are overwritten with 4 and 5. The last node stays unchanged.

Input: ({'val': 7, 'left': None, 'right': None}, [1, 2, 3])

Expected Output: {'val': 1, 'left': None, 'right': {'val': 2, 'left': None, 'right': {'val': 3, 'left': None, 'right': None}}}

Explanation: Overwrite the only existing node with 1, then append 2 and 3 as a right chain.

Input: ({'val': 1, 'left': None, 'right': None}, [])

Expected Output: {'val': 1, 'left': None, 'right': None}

Explanation: An empty target requires no change.

Input: (None, [9, 8])

Expected Output: {'val': 9, 'left': None, 'right': {'val': 8, 'left': None, 'right': None}}

Explanation: An empty tree becomes a pure right-child chain containing the target values.

Hints

  1. If you overwrite the first visited inorder nodes with target values in order, target becomes a prefix of the modified inorder traversal.
  2. Any remaining target values can be appended at the end of inorder by attaching a right-child chain to the original rightmost node.

Part 3: Minimum-Cost Edit Plan for Inorder Subsequence

You are given a binary tree of integers and an array target. Each allowed operation costs 1: overwrite the value of an existing node, or insert a new node anywhere so that it appears at a chosen position in the inorder order. Compute the minimum number of operations needed so that target becomes a subsequence of the tree's inorder traversal, and return one optimal edit plan. First flatten the tree to its inorder value sequence. Report edits using original inorder indices (0-based): ('overwrite', idx, value) means overwrite the idx-th original inorder node; ('insert_before', idx, value) means insert a new node so it appears immediately before original inorder index idx; idx == n means append after the last original node. If multiple inserts use the same idx, they are applied in the order listed. To make the output deterministic, when reconstructing an optimal plan from DP at state (i, j), use this priority: (1) use original node i for target[j] if that keeps the total cost optimal, recording an overwrite only if the values differ; (2) otherwise insert target[j] before i if that keeps the total cost optimal; (3) otherwise skip original node i.

Constraints

  • 0 <= number of nodes <= 200
  • 0 <= len(target) <= 200
  • -10^9 <= node values, target values <= 10^9
  • Duplicate values are allowed

Examples

Input: ({'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}, [1, 3])

Expected Output: (0, [])

Explanation: The target is already a subsequence of the inorder traversal [1, 2, 3].

Input: ({'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}, [1, 4, 3])

Expected Output: (1, [('overwrite', 1, 4)])

Explanation: Using the deterministic tie-break, overwrite original inorder index 1 (value 2) to 4.

Input: ({'val': 2, 'left': {'val': 1, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}, [3, 1])

Expected Output: (1, [('insert_before', 0, 3)])

Explanation: Insert 3 before original inorder index 0, then use the original 1.

Input: ({'val': 5, 'left': None, 'right': None}, [1])

Expected Output: (1, [('overwrite', 0, 1)])

Explanation: Overwrite the only original node.

Input: (None, [2, 2])

Expected Output: (2, [('insert_before', 0, 2), ('insert_before', 0, 2)])

Explanation: With no original nodes, both target values must be inserted.

Hints

  1. After converting the tree to its inorder sequence, the problem becomes sequence DP.
  2. At DP state (i, j), consider three choices: skip inorder[i], use inorder[i] for target[j] with cost 0 or 1, or insert target[j] with cost 1.
Last updated: May 9, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Count Candies from Unlockable Boxes - Airbnb (medium)
  • Find Optimal Property Combination - Airbnb (medium)
  • Determine Exact Layover Booking - Airbnb (medium)
  • Solve Linked-List and Iterator Problems - Airbnb
  • Implement Text Layout and Query Parsing - Airbnb (easy)