Fix a BST with two misplaced keys

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Fix a BST with Two Misplaced Keys

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 nulls are omitted. Return the corrected tree in the same level-order array format (with trailing nulls 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.

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.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Choose traversal based on the required output. DFS is natural for subtree computations, reconstruction, and range pruning; BFS is natural for level order or side views. Keep per-depth or per-position state when the output depends on columns, rows, or depths.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Most tree traversals are O(n) time and O(h) recursion stack for DFS or O(w) queue space for BFS, where h is height and w is maximum width.

Edge Cases and Tests

Empty tree, one node, skewed tree, duplicate values when reconstruction assumes uniqueness, deep recursion, and tie-breaking for same row/column nodes.