LeetCode Recover Binary Search Tree: O(1) Space Inorder Traversal (Morris Traversal)

Overview

LeetCode Recover Binary Search Tree: Find the inverse pair in the inorder traversal with O(1) Space by the so called Morris Traversal and swap the inverse pair

LeetCode Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

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

Solution: O(1) Space Inorder Traversal (Morris Traversal)

The basic idea is to in-order traverse the whole tree and find the reversed pair and fix them. The following are based on the same in-order traverse but using different space.

(1)  using average O(N) space. use perform regular in-order traverse on the whole tree and store all the node pointers in an allocated vector or array, find the reversed pair in the array, and swap the values pointed by the stored pointers. The allocated array cost O(N) space averagely

(2) average O(log N) space but O(N) in worst case. Still do in-order traverse but without the the allocated array in (1), this could be down by keeping two pointers prev and current which point to the consecutive nodes in the in-order sequence, during one pass in-order traverse, we keep comparing them (pre->val, current->val) and we can get the first and second pointers to the swapped wrong nodes. After finishing the in-order traverse, you swap back the two wrong nodes. And we are down. Since we do recursive in-order traverse, we still allocate additional memory in the stack which is O(hight of the tree), so the space we use is actually  average O(log N) space but O(N) in worst case. The following code implements this idea and is accepted by LeetCode OJ to pass this Recover Binary Search Tree probrolem:

class Solution {
    public:

        TreeNode *prev, *next;
        bool prevFound = false;
        void dfs(TreeNode *root) {
            if (NULL == root)
                return ;
            dfs(root->left);
            if (prev && prev->val > root->val)
                prevFound = true;
            if (!prevFound)
                prev = root;

            if (prevFound && root->val < prev->val) {
                next = root;
            }
            dfs(root->right);
        }

        void recoverTree(TreeNode *root) {
            if (NULL == root)
                return ;
            next = prev = NULL;
            prevFound = false;
            dfs(root);
            swap(prev->val, next->val);
        }
};

Alghouth this is not the truly constant space apporach, it indeed gives elegant and simpler implementation than the following so called “Morris Traversal”.

(3) real constant space. In order to get constant space, we have to be able to do the in-order traverse without using the stack, then we might need to get the help of the “threaded binary tree”. By following the threaded binary tree, we make use of the NULL node of the leaf node by making the right NULL child of the leaf node point to the next node in the in-order sequence, we are able to do the in-order traverse without using stack and thus constant memory, combing (2) we only need another two pointers Prev, Curret, to keep traversing the while tree in in-order and another two Ptr1, Ptr2 to keep record of the reversed nodes. Then then finish swapping them. And all these are be achieved by using constant number of pointers. This is constant space solution. This advanced algorithm is actually called “Morris Traversal”. I will give the code which pass the LeetCode OJ for this Recover Binary Search Tree problem and then add more explanation of how it works:

void recoverTree(TreeNode *root) {
    TreeNode *curr = root;

    TreeNode *ptr1 = NULL;
    TreeNode *ptr2 = NULL;
    TreeNode *prev = NULL;

    TreeNode *predecessor = NULL;
    while (curr) {
        if (NULL == curr->left) {
            if (prev && prev->val > curr->val) {
                ptr2 = curr;
                if (NULL == ptr1)
                    ptr1 = curr;
            }

            prev = curr;
            curr = curr->right;
        }
        else {
            predecessor = curr->left;

            while (predecessor->right != NULL && predecessor->right != curr)
                predecessor = predecessor->right;

            if (NULL == predecessor->right) {
                predecessor->right = curr;
                curr = curr->left;
            }
            else {
                if (prev && prev->val > curr->val) {
                    ptr2 = curr;
                    if (NULL == ptr1)
                        ptr1 = prev;
                }
                predecessor->right = NULL;
                prev = curr;
                curr = curr->right;
            }
        }
    }

    swap(ptr1->val, ptr2->val);
}

Several important notes on how the above code works correctly:

  1. if the curr->left == NULL, it means, either it is a leaf node, or it has no left subtree, then obviously, it is the right time to print the current node value out and go to curr->right for next processing
  2. if the curr->left != NULL, it means, we need to process the left subtree. And there are 2 cases which is determined by testing the right most leaf node of the left subtree, let’s call this node L, we test whether L->right is equal to the curr node or not
    • case 1: if so, then it means, the left subtree already finished processing, we need to set it back and print current value and go to curr->right
    • case 2: the left subtree is not finished processing, then L->right where L is the inorder predecessor need to be set to the curr and we go to the curr->left
  3. Do not set the prev pointer in case 2 which actually will disturb the correct order of (prev, curr) pointers.

Summary

LeetCode Recover Binary Search Tree: Find the inverse pair in the inorder traversal with O(1) Space by the so called Morris Traversal and swap the inverse pair

Written on June 16, 2013