Recover Binary Search Tree

Medium · Graphs · Explanation and code example

Morris Traversal

How it works

Morris traversal allows us to perform inorder traversal without using a stack or recursion, achieving O(1) space complexity. The technique works by temporarily modifying the tree structure: for each node with a left child, we find its inorder predecessor and create a temporary link back to the current node.

This temporary threading allows us to return to ancestor nodes after processing the left subtree without needing a stack. We can detect inversions during this traversal just like in the iterative approach, but without the extra space for a stack.

Steps

  1. Initialize pointers for node1, node2, prev, and curr (starting at root).
  2. While curr is not null:
    • If curr has no left child, process it (check for inversion with prev), update prev, and move to the right child.
    • If curr has a left child, find its inorder predecessor (rightmost node in left subtree).
      • If the predecessor's right pointer is null, create a thread to curr and move left.
      • If the predecessor's right pointer points to curr, remove the thread, process curr, update prev, and move right.
  3. After traversal, swap the values of node1 and node2.

Complexity

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

Things to watch for

Assuming Only One Inversion Exists

When two nodes are swapped in a BST, there can be either one or two inversions in the inorder sequence depending on whether the swapped nodes are adjacent. Assuming only one inversion and not checking for a second one causes incorrect identification of the swapped nodes.

Swapping Node References Instead of Values

The problem asks to recover the tree by swapping values, not by restructuring node pointers. Attempting to swap the actual node positions in the tree is unnecessarily complex and error-prone. Simply swap the val fields of the two identified nodes.

Incorrectly Identifying First and Second Nodes

In the first inversion, node1 is the larger (out-of-place) element, and node2 is the smaller one. If a second inversion is found, node2 should be updated to the smaller element of that inversion, while node1 remains unchanged. Mixing up which node to update at each inversion leads to swapping the wrong pair.

Python code example

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        node1 = node2 = prev = None
        curr = root

        while curr:
            if not curr.left:
                if prev and prev.val > curr.val:
                    node2 = curr
                    if not node1:
                        node1 = prev
                prev = curr
                curr = curr.right
            else:
                pred = curr.left
                while pred.right and pred.right != curr:
                    pred = pred.right

                if not pred.right:
                    pred.right = curr
                    curr = curr.left
                else:
                    pred.right = None
                    if prev and prev.val > curr.val:
                        node2 = curr
                        if not node1:
                            node1 = prev
                    prev = curr
                    curr = curr.right

        node1.val, node2.val = node2.val, node1.val

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode* node1 = nullptr;
        TreeNode* node2 = nullptr;
        TreeNode* prev = nullptr;
        TreeNode* curr = root;

        while (curr) {
            if (!curr->left) {
                if (prev && prev->val > curr->val) {
                    node2 = curr;
                    if (!node1) node1 = prev;
                }
                prev = curr;
                curr = curr->right;
            } else {
                TreeNode* pred = curr->left;
                while (pred->right && pred->right != curr) {
                    pred = pred->right;
                }

                if (!pred->right) {
                    pred->right = curr;
                    curr = curr->left;
                } else {
                    pred->right = nullptr;
                    if (prev && prev->val > curr->val) {
                        node2 = curr;
                        if (!node1) node1 = prev;
                    }
                    prev = curr;
                    curr = curr->right;
                }
            }
        }

        swap(node1->val, node2->val);
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations