Quick Overview

This question evaluates algorithm design and data-structure manipulation in the Coding & Algorithms domain, focusing on binary tree inorder traversal, subsequence detection, and computing the minimum edit operations under strict time and space constraints.

Verify and modify inorder subsequence

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Given a binary tree and a sequence of numbers, design an algorithm to check in O(n) time and O( 1) extra space whether the sequence is a subsequence of the tree’s inorder traversal. How would you modify the tree so that its inorder traversal contains the given sequence as a subsequence? What is the minimum number of operations (changing an existing node’s value or inserting a new node counts as 1) required to achieve this modification?

Quick Answer: This question evaluates algorithm design and data-structure manipulation in the Coding & Algorithms domain, focusing on binary tree inorder traversal, subsequence detection, and computing the minimum edit operations under strict time and space constraints.

Part 1: Verify an Inorder Subsequence with Morris Traversal

You are given a binary tree serialized in level-order form, where None represents a missing child, and a list of integers called sequence. Return True if sequence is a subsequence of the tree's inorder traversal, otherwise return False. The intended algorithmic idea is to scan the inorder traversal in O(n) time while using O(1) auxiliary traversal space via Morris traversal.

Constraints

  • 0 <= number of serialized entries in tree <= 100000
  • 0 <= len(sequence) <= 100000
  • If tree is non-empty, tree[0] is not None
  • Node values and sequence values are integers in the range [-10^9, 10^9]
  • Duplicate values are allowed

Examples

Input: ([2, 1, 3], [1, 3])

Expected Output: True

Explanation: The inorder traversal is [1, 2, 3], and [1, 3] appears in order.

Input: ([2, 1, 3], [3, 1])

Expected Output: False

Explanation: The values exist, but not in inorder subsequence order.

Hints

  1. You only need one pointer into sequence while scanning the inorder traversal.
  2. Morris traversal visits nodes in inorder without a recursion stack by temporarily threading predecessor pointers.

Part 2: Modify the Tree by Appending the Unmatched Inorder Suffix

You are given a binary tree serialized in level-order form and a target sequence. Construct a modified tree using this exact deterministic rule: first, scan the original tree's inorder traversal and greedily match the longest prefix of sequence; second, keep all original node values unchanged; third, if any suffix of sequence remains unmatched, attach new nodes containing that suffix as a right-child chain to the current inorder-last node. If the tree is empty, create a right-child chain from the entire sequence. Return the modified tree in level-order form, trimming trailing None values.

Constraints

  • 0 <= number of serialized entries in tree <= 10000
  • 0 <= len(sequence) <= 10000
  • If tree is non-empty, tree[0] is not None
  • Values are integers in the range [-10^9, 10^9]
  • Duplicate values are allowed

Examples

Input: ([2, 1, 3], [1, 4])

Expected Output: [2, 1, 3, None, None, None, 4]

Explanation: The original inorder is [1, 2, 3], which matches prefix [1]. The remaining value 4 is appended at the end as a new right child of the inorder-last node.

Input: ([2, 1, 3], [1, 2])

Expected Output: [2, 1, 3]

Explanation: The sequence is already a subsequence of the original inorder traversal, so no nodes are added.

Hints

  1. Greedily match as much of the sequence as possible during an inorder traversal of the original tree.
  2. Adding a right-child chain to the inorder-last node appends values at the very end of the inorder traversal.

Part 3: Minimum Operations to Force an Inorder Subsequence

You are given a binary tree serialized in level-order form and a target sequence. In one operation, you may either change the value of an existing node or insert a new node anywhere in the tree. Extra values in the inorder traversal are allowed. Compute the minimum number of operations needed so that the modified tree's inorder traversal contains sequence as a subsequence.

Constraints

  • 0 <= number of serialized entries in tree <= 2000
  • 0 <= len(sequence) <= 2000
  • If tree is non-empty, tree[0] is not None
  • Values are integers in the range [-10^9, 10^9]
  • Duplicate values are allowed

Examples

Input: ([2, 1, 3], [1, 3])

Expected Output: 0

Explanation: The inorder traversal is already [1, 2, 3], so the target sequence already appears.

Input: ([2, 1, 3], [1, 4, 3])

Expected Output: 1

Explanation: Keep 1 and 3, then either change the middle node to 4 or insert 4 once.

Hints

  1. A target value costs 0 only if you can keep some existing inorder node with the same value in the correct relative order.
  2. So the problem becomes: maximize how many target values are already matched in order, then pay 1 for every remaining target value.

Loading coding console...