Question
Given a binary tree and a sequence of numbers, design an algorithm to check in O(n) time and O(
-
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
-
required to achieve this modification?