Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Fix a BST with two misplaced keys states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Fix a BST with two misplaced keys

Company: TikTok

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given the root of a binary search tree in which exactly two nodes’ keys were accidentally swapped. Restore the tree so that its in-order traversal is strictly non-decreasing, without changing the tree’s structure. Aim for O(n) time and O( 1) extra space; discuss an approach that does not use recursion or an explicit stack. Describe how you would detect the misplaced nodes, handle both adjacent and non-adjacent violations, and analyze time/space complexity.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Fix a BST with two misplaced keys states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given the root of a binary search tree (BST) in which **exactly two** nodes' keys were accidentally swapped. Restore the tree so that its in-order traversal is strictly increasing again, **without changing the tree's structure** (only node values may change). The tree is provided as a level-order array (LeetCode style): `null` marks a missing child, and trailing `null`s are omitted. Return the corrected tree in the same level-order array format (with trailing `null`s trimmed). Your detection must handle both cases: - **Adjacent violation** — the two swapped nodes are next to each other in the in-order sequence (exactly one descending step). - **Non-adjacent violation** — the two swapped nodes are far apart (two descending steps in the in-order sequence). Aim for **O(n)** time and **O(1)** extra space. Discuss an approach that uses neither recursion nor an explicit stack (Morris traversal). **Example 1** ``` Input: [1, 3, null, null, 2] Output: [3, 1, null, null, 2] ``` In-order is 3,2,... so 1 and 3 were swapped. Swapping them back gives a valid BST. **Example 2** ``` Input: [3, 1, 4, null, null, 2] Output: [2, 1, 4, null, null, 3] ``` The non-adjacent nodes 2 and 3 were swapped.

Constraints

  • The number of nodes is in the range [1, 10^4] for non-empty trees; the empty-tree case ([]) is also handled.
  • Exactly two nodes' keys were swapped.
  • Node values fit in a 32-bit signed integer and may be negative.
  • The tree structure must not change — only node values may be corrected.
  • Input/output use level-order arrays with null for missing children and trailing nulls trimmed.

Examples

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

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

Explanation: Adjacent violation: in-order is 3,2,1 region; swapping 1 and 3 restores increasing order.

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

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

Explanation: Non-adjacent violation: keys 2 and 3 were swapped; restoring them yields a valid BST.

Hints

  1. An in-order traversal of a valid BST is strictly increasing. After swapping two keys, the in-order sequence has either one or two positions where a value is greater than the value that follows it.
  2. Walk the in-order sequence tracking the previous node. The FIRST time you see prev.val > cur.val, record `first = prev`. EVERY time it happens, record `second = cur`. Then swap first.val and second.val.
  3. For an adjacent violation there is exactly one descending step, so first = prev and second = cur of that single step. For a non-adjacent violation there are two descending steps; first comes from the earlier step and second from the later step.
  4. To hit O(1) extra space without recursion or a stack, use Morris traversal: thread each node's in-order predecessor's right pointer to the node, then undo the thread on the way back.

Loading coding console...