What is the time complexity of Recover Binary Search Tree?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Recover Binary Search Tree?

This problem uses Tree, Depth-First Search, Binary Search Tree, Binary Tree. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Recover Binary Search Tree?

Insight 1: In-order traversal of a BST yields a sorted sequence. Deviations from this sorted order indicate the swapped nodes. Insight 2: Morris traversal provides an in-order traversal in O(1) space, fulfilling the follow-up requirement.

Which companies ask LeetCode 99. Recover Binary Search Tree in interviews?

This problem is frequently asked at Amazon, Apple, Bloomberg, Microsoft, TikTok and 1 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Recover Binary Search Tree - LeetCode 99 Solution

Q: How to solve Recover Binary Search Tree?

The solution utilizes Morris traversal (threaded binary tree traversal) to perform an in-order traversal of the BST in O(1) space. During the traversal, it keeps track of the previous node visited and checks if the current node's value is less than the previous node's value. If this condition is met, it indicates a violation of the BST property, meaning that we've encountered a node that's out of order due to the swap. The first time this happens, we mark the 'previous node' as the 'first_node'. Subsequent violations indicate the second misplaced node. The last violation is identified as the 'second_node'. After the entire tree is traversed, the values of 'first_node' and 'second_node' are swapped to recover the BST.

Recover Binary Search Tree - Complete Solution Guide

Recover Binary Search Tree is LeetCode problem 99, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem asks us to recover a Binary Search Tree (BST) where exactly two nodes have been swapped. The goal is to identify these two swapped nodes and restore the BST property by swapping their values back. The structure of the tree must remain unchanged. Input is the root of the corrupted BST, and the output is the modified (recovered) BST. The constraints specify the size of the tree (2 to 1000 nodes) and the range of node values (-2^31 to 2^31 - 1).

Solution Approach

The solution utilizes Morris traversal (threaded binary tree traversal) to perform an in-order traversal of the BST in O(1) space. During the traversal, it keeps track of the previous node visited and checks if the current node's value is less than the previous node's value. If this condition is met, it indicates a violation of the BST property, meaning that we've encountered a node that's out of order due to the swap. The first time this happens, we mark the 'previous node' as the 'first_node'. Subsequent violations indicate the second misplaced node. The last violation is identified as the 'second_node'. After the entire tree is traversed, the values of 'first_node' and 'second_node' are swapped to recover the BST.

Step-by-Step Algorithm

Step 1: Initialize `first_node`, `second_node` to None, and `prev_node` to a TreeNode with value negative infinity to handle the first comparison correctly.
Step 2: Start Morris traversal. While `current` is not None, do:
Step 3: If `current` does not have a left child:
Step 4: Check if `prev_node.val > current.val`. If true, then:
Step 5: If `first_node` is None, assign `prev_node` to `first_node`.
Step 6: Assign `current` to `second_node`.
Step 7: Update `prev_node` to `current`.
Step 8: Move to the right child: `current = current.right`.
Step 9: Else (if `current` has a left child):
Step 10: Find the in-order predecessor of `current`.
Step 11: If the predecessor's right child is None, then:
Step 12: Set predecessor's right child to `current` (create the thread).
Step 13: Move to the left child: `current = current.left`.
Step 14: Else (predecessor's right child is `current`):
Step 15: Remove the thread: set predecessor's right child to None.
Step 16: Check if `prev_node.val > current.val`. If true, then:
Step 17: If `first_node` is None, assign `prev_node` to `first_node`.
Step 18: Assign `current` to `second_node`.
Step 19: Update `prev_node` to `current`.
Step 20: Move to the right child: `current = current.right`.
Step 21: After the traversal, swap the values of `first_node` and `second_node` if they exist.

Key Insights

Insight 1: In-order traversal of a BST yields a sorted sequence. Deviations from this sorted order indicate the swapped nodes.
Insight 2: Morris traversal provides an in-order traversal in O(1) space, fulfilling the follow-up requirement.
Insight 3: We need to identify the first node that violates the sorted order and the second node that contributes to the violation. These are the nodes to be swapped.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Tree, Depth-First Search, Binary Search Tree, Binary Tree.

Companies

Asked at: Amazon, Apple, Bloomberg, Microsoft, TikTok, Yahoo.

Recover Binary Search Tree | LeetCode 99

Medium

Tree Depth-First Search Binary Search Tree Binary Tree

Time: O(n)Space: O(1)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode first_node = null;
    TreeNode second_node = null;
    TreeNode prev_node = new TreeNode(Integer.MIN_VALUE);
    public void recoverTree(TreeNode root) {
        
        TreeNode current = root;
        while (current != null) {
            if (current.left == null) {
                if (prev_node.val > current.val) {
                    if (first_node == null) {
                        first_node = prev_node;
                    }
                    second_node = current;
                }
                
                prev_node = current;
                current = current.right;
            } else {
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }
                
                if (predecessor.right == null) {
                    predecessor.right = current;
                    current = current.left;
                } else {
                    predecessor.right = null;
                    
                    if (prev_node.val > current.val) {
                        if (first_node == null) {
                            first_node = prev_node;
                        }
                        second_node = current;
                    }
                    
                    prev_node = current;
                    current = current.right;
                }
            }
        }
        
        if (first_node != null && second_node != null) {
            int temp = first_node.val;
            first_node.val = second_node.val;
            second_node.val = temp;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 99: Recover Binary Search Tree - Detailed explanation and solution approaches.

Topics

Tree Depth-First Search Binary Search Tree Binary Tree

Companies

AmazonAppleBloombergMicrosoftTikTokYahoo

Stats

Difficulty:Medium

Languages:4

Companies:6

Problem #:99

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

21 steps

1
Step 1: Initialize `first_node`, `second_node` to None, and `prev_node` to a TreeNode with value negative infinity to handle the first comparison correctly.
2
Step 2: Start Morris traversal. While `current` is not None, do:
3
Step 3: If `current` does not have a left child:
4
Step 4: Check if `prev_node.val > current.val`. If true, then:
5
Step 5: If `first_node` is None, assign `prev_node` to `first_node`.
6
Step 6: Assign `current` to `second_node`.
7
Step 7: Update `prev_node` to `current`.
8
Step 8: Move to the right child: `current = current.right`.
9
Step 9: Else (if `current` has a left child):
10
Step 10: Find the in-order predecessor of `current`.
11
Step 11: If the predecessor's right child is None, then:
12
Step 12: Set predecessor's right child to `current` (create the thread).
13
Step 13: Move to the left child: `current = current.left`.
14
Step 14: Else (predecessor's right child is `current`):
15
Step 15: Remove the thread: set predecessor's right child to None.
16
Step 16: Check if `prev_node.val > current.val`. If true, then:
17
Step 17: If `first_node` is None, assign `prev_node` to `first_node`.
18
Step 18: Assign `current` to `second_node`.
19
Step 19: Update `prev_node` to `current`.
20
Step 20: Move to the right child: `current = current.right`.
21
Step 21: After the traversal, swap the values of `first_node` and `second_node` if they exist.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The Morris traversal ensures that we visit each node a constant number of times, leading to O(n) time complexity. Since we're only using a few pointer variables (first_node, second_node, prev_node, current, predecessor), the space complexity is constant.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

In-order Traversal with O(n) Space

Perform a standard in-order traversal and store the node values in an array. Then, identify the swapped elements in the sorted array and swap the corresponding node values in the tree.

Time: O(n)Space: O(n)

Trade-offs: This approach is simpler to implement but violates the O(1) space constraint. Use this if space isn't a concern or as a baseline for understanding the problem.

✨

Key Insights

1Insight 1: In-order traversal of a BST yields a sorted sequence. Deviations from this sorted order indicate the swapped nodes.
2Insight 2: Morris traversal provides an in-order traversal in O(1) space, fulfilling the follow-up requirement.
3Insight 3: We need to identify the first node that violates the sorted order and the second node that contributes to the violation. These are the nodes to be swapped.

📚

Key Terms Explained

For Students

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Adjacent swapped nodes. The algorithm correctly identifies and swaps adjacent nodes because it compares each node with its immediate predecessor.
Edge case 2: Swapped nodes are far apart. The algorithm identifies the first and last out-of-order nodes, regardless of their distance in the tree.
Edge case 3: Only two nodes exist and they are swapped. The algorithm correctly identifies and swaps these two nodes.
Edge case 4: The root node is one of the swapped nodes. The initial 'prev_node' with a value of negative infinity ensures that the root is compared correctly when it's the second node, even if it's smaller than the left-most node of the tree. Also, when the root is the first node (e.g. [3,1,null,null,2] with root being 3, and the swap happens between 3 and 2), prev_node becomes the in-order predecessor, which is 1 in this case, and the check `prev_node.val > current.val` correctly identifies the two swapped nodes.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly identifying the swapped nodes. It's crucial to find the *first* node that violates the sorted order (first_node) and the *last* node that violates the sorted order (second_node). Simply swapping the first two out-of-order nodes can be wrong.

✗Common mistake 2: Failing to handle the case where the swapped nodes are adjacent. The logic should be able to identify and swap adjacent nodes.

✗Common mistake 3: Not correctly removing the thread in Morris traversal, leading to an infinite loop.

✗Common mistake 4: Not handling the edge case where the first out-of-order node appears at the root.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data corruption in a database. If a database index (which is often a tree structure) becomes corrupted due to memory errors or software bugs, this algorithm could be adapted to identify and potentially correct the inconsistencies.

🏦Real-world scenario 2: Network routing tables. Routing tables in networks are often organized as tree structures. If entries in the routing table become corrupted or misconfigured, a similar recovery algorithm can be used to restore the table's integrity and ensure proper routing of network traffic.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Most tree problems can be solved recursively. The base case is usually a null node. Think about what information needs to flow up vs down the tree.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Not handling null nodes properly. Always check if the current node exists before accessing its children.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 29

❓

Frequently Asked Questions

What is the difference between DFS and BFS for trees?

DFS (using recursion or stack) explores depth-first, useful for path-finding and backtracking problems. BFS (using queue) explores level-by-level, ideal for finding shortest paths or processing nodes by depth. Choose based on whether level information matters.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Recover Binary Search Tree"?

For this medium-level Tree problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?