How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at TikTok during technical interviews.

Fix a BST with two misplaced keys | TikTok Coding Question

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.

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

Expected Output: [2, 1, 3]

Explanation: Left child 3 and right child 1 violate BST order; swapping them fixes it.

Input: ([1],)

Expected Output: [1]

Explanation: Single node — trivially valid, returned unchanged.

Input: ([],)

Expected Output: []

Explanation: Empty tree edge case — returned unchanged.

Input: ([10, 5, 8, 2, 20],)

Expected Output: [10, 5, 20, 2, 8]

Explanation: Non-adjacent violation in a deeper unbalanced tree: 8 and 20 were swapped.

Hints

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.
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.
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.
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.

Quick Overview