Home Problem Set Companies Projects Live Scene Contribute

Loading Question...

Recover Binary Search Tree - AMAZON ML SUMMER SCHOOL - AMAZON ML SUMMER SCHOOL Interview Question | Codinzhub

Home Problem Set Companies Projects Live Scene Contribute

Recover Binary Search Tree - AMAZON ML SUMMER SCHOOL

Two elements of a Binary Search Tree (BST), represented by root A are swapped by mistake. Tell us the 2 values, when swapped, will restore the Binary Search Tree (BST). A solution using O(n) space is pretty straightforward. Could you devise a constant space solution? Note: The 2 values must be returned in ascending order

Example 1:

Input:[{"val":1,"left":{"val":3,"left":null,"right":null},"right":{"val":2,"left":null,"right":null}}]

Output:[1,3]

Example 2:

Input:[{"val":2,"left":{"val":1,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}]

Output:[2,3]

Constraints:

1 <= size of tree <= 100000

solution.cpp

Run code to see test results

00:00 / 69:42

Recover Binary Search Tree - AMAZON ML SUMMER SCHOOL

MediumMed•939 views

Example 1:

Input:[{"val":1,"left":{"val":3,"left":null,"right":null},"right":{"val":2,"left":null,"right":null}}]

Output:[1,3]

Example 2:

Input:[{"val":2,"left":{"val":1,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}]

Output:[2,3]

Constraints:

1 <= size of tree <= 100000

MediumMed•939 views

Time Complexity

Space Complexity

Asked at

AMAZON ML SUMMER SCHOOL

Author: Amit Dayal

Software Engineer

Expert in Data Structures & Algorithms. Building tools to help developers crack FAANG interviews.

Reviewed by Senior Engineers

GitHub LinkedIn

Up Next

Future First MCQS (6m Intern + PPO) - IIIT UNA

Future First • Pending

Missing Number in Sequence - ARM Online Assessment DTU

ARM • Pending

Circular Elimination Game - ARM Online Assessment DTU

ARM • Pending

The Pair Sum (Easy Version) - Adobe Hackathon 2026

Adobe • Pending

Design an ATM System - Adobe Hackathon 2026

Adobe Hackthon 2026 Discussion • Pending

Last updated Aug 2026