Is Recover Binary Search Tree easy or hard?

Recover Binary Search Tree is rated Medium on LeetCode. Detecting swapped nodes using in-order traversal is straightforward, but implementing the optimal O(1) space Morris Traversal requires deeper understanding of tree traversal techniques.

Recover Binary Search Tree Python/Java solution

Typical Python or Java solutions perform an in-order traversal, track the previous node, and detect two nodes where the sorted order breaks. After traversal, swapping those node values restores the BST in O(n) time.

How to solve Recover Binary Search Tree in O(n)?

Perform an in-order traversal and track the previous visited node. Whenever prev.val is greater than the current node value, record the misplaced nodes. After traversal finishes, swap the values of the two identified nodes to restore the BST.

What is the best approach for Recover Binary Search Tree?

Morris Traversal is considered the best approach because it recovers the BST in O(n) time using O(1) extra space. It performs an in-order traversal without recursion or a stack while detecting the two misplaced nodes through ordering violations.

Is Recover Binary Search Tree asked at Google/Amazon/Meta?

Recover Binary Search Tree is a common interview problem at companies like Amazon, Google, and Meta because it tests understanding of BST properties, in-order traversal, and space optimization techniques like Morris Traversal.

What data structure is used in Recover Binary Search Tree?

The problem operates on a Binary Search Tree. The solution relies on in-order traversal, which can be implemented using recursion, an explicit stack, or Morris Traversal for constant auxiliary space.

What is the time complexity of Recover Binary Search Tree?

Both common solutions run in O(n) time where n is the number of nodes in the tree. Each node is visited at most once during the in-order traversal used to detect the swapped nodes.

Description Solution Video 16:55

99. Recover Binary Search Tree

Medium60.9% acceptance8 companies

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Example 1:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints:

The number of nodes in the tree is in the range [2, 1000].
-2³¹ <= Node.val <= 2³¹ - 1

Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?

Asked at 8 companies

Medianet

Google Amazon Microsoft D. E. Shaw Bloomberg Tiktok Meta

Topics

16:55

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def recoverTree(self, root: Optional[TreeNode]) -> None:
9        """
10        Do not return anything, modify root in-place instead.
11        """
12        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,3,null,null,2]

Input

[3,1,4,null,null,2]

Your code is saved on this device.Solution