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•366 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•366 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

Find Total Efficiency

Amazon • Pending

Best TV Shows in Genre - HackerRank Forward Deployed Engineer

Hackerrank • Pending

SQL: Accounting Software Debit and Credit Report - HackerRank Forward Deployed Engineer

Hackerrank • Pending

Username Strength Checker - HackerRank Forward Deployed Engineer

Hackerrank • Pending

Streetlight Motion Detection Duration - AMAZON ML SUMMER SCHOOL

AMAZON ML SUMMER SCHOOL • Pending

Last updated Jun 2026