Verify and modify inorder subsequence
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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
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.
Input: ([], [])
Expected Output: True
Explanation: The empty sequence is a subsequence of the empty traversal.
Input: ([], [1])
Expected Output: False
Explanation: A non-empty sequence cannot be a subsequence of an empty traversal.
Input: ([4, 2, 6, 1, 3, 5, 7], [1, 3, 7])
Expected Output: True
Explanation: The inorder traversal is [1, 2, 3, 4, 5, 6, 7], so [1, 3, 7] is a subsequence.
Solution
def solution(tree, sequence):
from collections import deque
class Node:
__slots__ = ('val', 'left', 'right')
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build(data):
if not data or data[0] is None:
return None
root = Node(data[0])
q = deque([root])
i = 1
while q and i < len(data):
node = q.popleft()
if i < len(data):
v = data[i]
i += 1
if v is not None:
node.left = Node(v)
q.append(node.left)
if i < len(data):
v = data[i]
i += 1
if v is not None:
node.right = Node(v)
q.append(node.right)
return root
if not sequence:
return True
root = build(tree)
if root is None:
return False
j = 0
cur = root
while cur is not None:
if cur.left is None:
if j < len(sequence) and cur.val == sequence[j]:
j += 1
cur = cur.right
else:
pred = cur.left
while pred.right is not None and pred.right is not cur:
pred = pred.right
if pred.right is None:
pred.right = cur
cur = cur.left
else:
pred.right = None
if j < len(sequence) and cur.val == sequence[j]:
j += 1
cur = cur.right
return j == len(sequence)
Time complexity: O(n), where n is the number of tree nodes.. Space complexity: O(1) auxiliary traversal space for the subsequence check itself using Morris traversal; this runnable wrapper also uses O(n) space to deserialize the level-order input into node objects..
Hints
- You only need one pointer into sequence while scanning the inorder traversal.
- 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
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.
Input: ([], [5, 6])
Expected Output: [5, None, 6]
Explanation: An empty tree becomes a right-skewed chain 5 -> 6.
Input: ([7], [])
Expected Output: [7]
Explanation: An empty target sequence needs no modification.
Input: ([], [])
Expected Output: []
Explanation: Both the tree and sequence are empty, so the result is an empty tree.
Solution
def solution(tree, sequence):
from collections import deque
class Node:
__slots__ = ('val', 'left', 'right')
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build(data):
if not data or data[0] is None:
return None
root = Node(data[0])
q = deque([root])
i = 1
while q and i < len(data):
node = q.popleft()
if i < len(data):
v = data[i]
i += 1
if v is not None:
node.left = Node(v)
q.append(node.left)
if i < len(data):
v = data[i]
i += 1
if v is not None:
node.right = Node(v)
q.append(node.right)
return root
def build_chain(values):
if not values:
return None
root = Node(values[0])
cur = root
for v in values[1:]:
cur.right = Node(v)
cur = cur.right
return root
def matched_prefix(root, seq):
stack = []
cur = root
j = 0
while stack or cur is not None:
while cur is not None:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if j < len(seq) and cur.val == seq[j]:
j += 1
cur = cur.right
return j
def serialize(root):
if root is None:
return []
out = []
q = deque([root])
while q:
node = q.popleft()
if node is None:
out.append(None)
else:
out.append(node.val)
q.append(node.left)
q.append(node.right)
while out and out[-1] is None:
out.pop()
return out
root = build(tree)
if root is None:
return serialize(build_chain(sequence))
j = matched_prefix(root, sequence)
if j < len(sequence):
tail = root
while tail.right is not None:
tail = tail.right
for v in sequence[j:]:
tail.right = Node(v)
tail = tail.right
return serialize(root)
Time complexity: O(n + m + s), where n is the number of original tree nodes, m is len(sequence), and s is the size of the returned serialization.. Space complexity: O(n + s) because the runnable solution deserializes the tree and also stores the serialized output..
Hints
- Greedily match as much of the sequence as possible during an inorder traversal of the original tree.
- 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
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.
Input: ([1], [2, 3])
Expected Output: 2
Explanation: There are no exact inorder matches with the target, so two target values must be created using two operations.
Input: ([], [])
Expected Output: 0
Explanation: No changes are required.
Input: ([1, None, 2], [2, 1])
Expected Output: 1
Explanation: The original inorder is [1, 2]. One insertion can make [2, 1] appear as a subsequence.
Solution
def solution(tree, sequence):
from collections import deque
class Node:
__slots__ = ('val', 'left', 'right')
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build(data):
if not data or data[0] is None:
return None
root = Node(data[0])
q = deque([root])
i = 1
while q and i < len(data):
node = q.popleft()
if i < len(data):
v = data[i]
i += 1
if v is not None:
node.left = Node(v)
q.append(node.left)
if i < len(data):
v = data[i]
i += 1
if v is not None:
node.right = Node(v)
q.append(node.right)
return root
if not sequence:
return 0
root = build(tree)
m = len(sequence)
dp = [0] * (m + 1)
def feed(value):
prev = 0
for j in range(1, m + 1):
temp = dp[j]
if value == sequence[j - 1]:
dp[j] = prev + 1
elif dp[j - 1] > dp[j]:
dp[j] = dp[j - 1]
prev = temp
cur = root
while cur is not None:
if cur.left is None:
feed(cur.val)
cur = cur.right
else:
pred = cur.left
while pred.right is not None and pred.right is not cur:
pred = pred.right
if pred.right is None:
pred.right = cur
cur = cur.left
else:
pred.right = None
feed(cur.val)
cur = cur.right
lcs = dp[m]
return m - lcs
Time complexity: O(n * m), where n is the number of tree nodes and m is len(sequence).. Space complexity: O(m) for the dynamic programming table, plus O(n) space in this runnable wrapper to deserialize the tree from its level-order representation..
Hints
- A target value costs 0 only if you can keep some existing inorder node with the same value in the correct relative order.
- So the problem becomes: maximize how many target values are already matched in order, then pay 1 for every remaining target value.