Recover Binary Search Tree

Difficulty Level Hard
Frequently asked in Amazon ByteDance Microsoft Oracle Uber
Binary Search Tree Binary Tree Depth First Search TreeViews 3094

Consider a binary search tree, two nodes of the tree have been swapped, design an algorithm to recover the binary search Tree.

Example

Consider the binary search tree given below whose two nodes have been swapped as input.

Recover Binary Search Tree

Incorrect nodes on the BST are detected(highlighted) and then swapped to obtain the correct BST.

Recover Binary Search Tree

Below is the corrected output BST obtained after swapping the incorrect nodes.

Recover Binary Search Tree

Types of Solution for Recover Binary Search Tree

  1. Naive
  2. Recursive
  3. Iterative
  4. Morris Traversal

 

Naive

Approach for Recover Binary Search Tree

Use vector to store all the elements of the tree using inorder traversal, sort this vector. Again, Perform inorder traversal of the tree and assign values from sorted vector to tree nodes one by one.

Algorithm

  1. Perform inorder traversal of the tree and store the traversal in a dynamic array.
  2. Sort the dynamic array using insertion sort(for minimum complexity).
  3. Perform the inorder traversal again and change the node values to values from the sorted array.
  4. Return the root node of the corrected binary search tree.

Recover Binary Search Tree

Implementation

C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

// function that performs inorder traversal based on the mode
/*
Their are 3 modes : 
1. traversal ('t') : simply perform traversal
2. storage ('s') : store data of tree into a vector
3. modify ('m'): store data of vector into a tree
*/
void inorder(Node *root,vector <int> &arr,char mode)
{
    if(!root)
    return;
    
    inorder(root->left,arr,mode);
    if(mode == 't')
    cout<<root->data<<" ";
    else if(mode == 's')
    arr.push_back(root->data);
    else if(mode == 'm')
    {
        int n = arr.size();
        root->data = arr[n-1];
        arr.pop_back();
    }
    inorder(root->right,arr,mode);
}

// function that corrects the BST and returns it's root
Node* fixBST(Node *root)
{
    // array to store inorder traversal
    vector <int> arr;
    // store the inorder traversal into arr
    inorder(root,arr,'s');
    
    // apply insertion sort to arr
    // insertion sort is used to minimize time complexity to o(n)
    int i,j,key; 
    for (i = 1; i < arr.size(); i++) 
    { 
        key = arr[i]; 
        j = i - 1; 
        while (j >= 0 && arr[j] < key) 
        { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
    
    // perform inorder on tree and modify the the node value of tree
    inorder(root,arr,'m');
    return root;
}


int main()
{
    /* create the incorrect BST*/
    Node *root = new Node(4);
    root->left = new Node(7);
    root->right = new Node(6);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(2);
    
    vector <int> arr;
    
    cout<<"Inorder traversal before : ";
    inorder(root,arr,'t');
      
    root = fixBST(root);
    
    cout<<endl;
    
    cout<<"Inorder traversal after : "; 
    inorder(root,arr,'t');
    return 0;
}
Inorder traversal before : 1 7 3 4 5 6 2 
Inorder traversal after : 1 2 3 4 5 6 7
Java Program
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    // function that performs inorder traversal based on the mode
    /*
    Their are 3 modes : 
    1. traversal ('t') : simply perform traversal
    2. storage ('s') : store data of tree into a vector
    3. modify ('m'): store data of vector into a tree
    */
    static void inorder(Node root,ArrayList <Integer> arr,char mode)
    {
        if(root == null)
        return;
        
        inorder(root.left,arr,mode);
        if(mode == 't')
        System.out.print(root.data+" ");
        else if(mode == 's')
        arr.add(root.data);
        else if(mode == 'm')
        {
            int n = arr.size();
            root.data = arr.get(n-1);
            arr.remove(n-1);
        }
        inorder(root.right,arr,mode);
    }
    
    // function that corrects the BST and returns it's root
    static Node fixBST(Node root)
    {
        // array to store inorder traversal
        ArrayList <Integer> arr = new ArrayList<>();
        // store the inorder traversal into arr
        inorder(root,arr,'s');
        
        // apply insertion sort to arr
        // insertion sort is used to minimize time complexity to o(n)
        int i,j,key; 
        for (i = 1; i < arr.size(); i++) 
        { 
            key = arr.get(i); 
            j = i - 1; 
            while (j >= 0 && arr.get(j) < key) 
            { 
                arr.set(j+1,arr.get(j)); 
                j = j - 1; 
            } 
            arr.set(j+1,key); 
        } 
        
        // perform inorder on tree and modify the the node value of tree
        inorder(root,arr,'m');
        return root;
    }
    
    public static void main (String[] args) 
    {
        /* create the incorrect BST*/
        Node root = new Node(4);
        root.left = new Node(7);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(2);
        
        ArrayList <Integer> arr = new ArrayList<>();
        
        System.out.print("Inorder traversal before : ");
        inorder(root,arr,'t');
        
        root = fixBST(root);
        
        System.out.println();
        System.out.print("Inorder traversal after : ");         
        inorder(root,arr,'t');
    }

}
Inorder traversal before : 1 7 3 4 5 6 2 
Inorder traversal after : 1 2 3 4 5 6 7

Complexity Analysis for Recover Binary Search Tree

  • Time Complexity : T(n) = O(n)
  • Space Complexity : A(n) = O(n)

Recursive

Approach for Recover Binary Search Tree

  1. Consider the Tree given in the above example. The nodes of the BST can be swapped in two ways.
  2. 1st way: 2 non-adjacent tree nodes are swapped (i.e. these nodes have at least one node between them. for ex: inorder traversal of the tree where non-adjacent nodes are swapped is: 1 7 3 4 5 6 2. As we observe 2 and 7 are swapped from their respective positions.
    1. We perform the inorder traversal and use first and second variables to store the two incorrectly placed nodes. we use prev to store the previous node visited before the current (root) node during inorder traversal.
    2. During inorder traversal, we find a node that violates the BST order. i.e. prev->data > root->data(where root is the current node being visited), we store prev into first and root into second.
    3. During further traversal, if we find another node that violates the BST criteria (as mentioned above), but this time the first node has been already assigned a value. so we assign the current node to second.
    4. After the traversal is over, we swap the data stored in the first and second nodes.
  3. 2nd way: 2 adjacent nodes are swapped (i.e. the nodes are parent-child pair).for ex: inorder traversal of the tree where adjacent nodes are swapped is: 1 2 4 3 5 6 7. As we observe 3 and 4 are swapped from their respective positions.
    1. We perform the inorder traversal and use first and second variables to store the two incorrectly placed nodes. we use prev to store the previous node visited before the current (root) node during inorder traversal.
    2. During inorder traversal, we find a node that violates the BST order. i.e. prev->data > root->data(where root is the current node being visited), we store prev into first and root into second.
    3. After the traversal is over, we swap the data stored in the first and second nodes.

Algorithm

  1. Define prev(stores previous nodes in traversal), first(stores first node out of order), second(stores second node out of order) variables to store various tree node addresses.
  2. Perform simple inorder traversal.
  3. If during inorder traversal, we find a node that violates the BST order. i.e. prev->data > root->data.we store prev into first and root into second.
  4. During further traversal, if we find another node that violates the BST criteria,i.e. prev->data > root->data. but this time the first node had been already assigned a value. so we assign the current node to second.
  5. After execution of inorder traversal. swap the data of first and second nodes.The tree is fixed.

Recover Binary Search Tree

Implementation

C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};
/* function that performs inorder traversal 
and checks for the incorrectly set nodes*/
void inorderFix(Node *root,Node* &prev,Node* &first,Node* &second)
{
    if(root == NULL)
    return;
    
    inorderFix(root->left,prev,first,second);
    
    if(prev != NULL && prev->data > root->data)
    {
        // first misordering found
        if(first == NULL)
        {
            first = prev;
            second = root;
        }
        
        // second misordering found (if exists)
        else
        second = root;
    }
    
    prev = root;
    
    inorderFix(root->right,prev,first,second);
}
// function that corrects the BST and returns it's root
Node* fixBST(Node *root)
{
    Node *prev,*first,*second;
    prev = first = second = NULL;
    
    inorderFix(root,prev,first,second);
    swap(first->data,second->data);
    
    return root;
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /* create the incorrect BST*/
    Node *root = new Node(4);
    root->left = new Node(7);
    root->right = new Node(6);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(2);
    
    cout<<"Inorder traversal before : ";
    inorder(root);
    
    root = fixBST(root);
    cout<<endl;
    
    cout<<"Inorder traversal after : ";
    inorder(root);
    
    return 0;
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7
Java Program
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    /* function that performs inorder traversal 
    and checks for the incorrectly set nodes*/
    static void inorderFix(Node root,ArrayList <Node> nodes)
    {
        if(root == null)
        return;
        
        inorderFix(root.left,nodes);
        
        if(nodes.get(0) != null && nodes.get(0).data > root.data)
        {
            // first misordering found
            if(nodes.get(1) == null)
            {
                // first is set to previous
                nodes.set(1,nodes.get(0));
                // second is set to current node
                nodes.set(2,root);
            }
            // second misordering found (if exists)
            else
            nodes.set(2,root);
        }
        
        // 1st element of ArrayList stores previous nodes
        nodes.set(0,root);
        
        inorderFix(root.right,nodes);
    }
    // function that corrects the BST and returns it's root
    /*
    here,
    prev -> nodes.get(0)
    first -> nodes.get(1)
    second -> nodes.get(2)
    */
    static Node fixBST(Node root)
    {
        // we use ArrayList to store previous(nodes[0]),first(nodes[1]) and second(nodes[2])
        // initially all nodes are set to null
        ArrayList <Node> nodes = new ArrayList<>(Arrays.asList(null,null,null));
        inorderFix(root,nodes);
        
        // swap the values of the nodes
        int temp = nodes.get(1).data;
        nodes.get(1).data = nodes.get(2).data;
        nodes.get(2).data = temp;
        
        return root;
    }
    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /* create the incorrect BST*/
        Node root = new Node(4);
        root.left = new Node(7);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(2);
        
        System.out.print("Inorder Traversal before : ");
        inorder(root);
        
        root = fixBST(root);
        System.out.println();
        
        System.out.print("Inorder Traversal after : ");
        inorder(root);
        
    }
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7

Complexity Analysis for Recover Binary Search Tree

  • Time Complexity : T(n) = O(n)
  • Space Complexity : A(n) = O(n), recursion stack space used.

Iterative

Approach for Recover Binary Search Tree

The idea is to convert the above recursive code into an iterative code.

Algorithm

  1. Define prev(stores previous nodes in traversal), first(stores first node out of order), second(stores second node out of order) variables to store various tree node addresses.
  2. Perform simple inorder traversal.
  3. If during inorder traversal, we find a node that violates the BST order. i.e. prev->data > root->data.we store prev into first and root into second.
  4. During further traversal, if we find another node that violates the BST criteria,i.e. prev->data > root->data. but this time the first node had been already assigned a value. so we assign the current node to second.
  5. After execution of inorder traversal. swap the data of the first and second nodes. The tree is fixed.

Implementation

C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};
 
// function that corrects the BST by performing iterative inorder 
// and returns it's root
Node* fixBST(Node *root)
{
    Node *prev,*first,*second;
    prev = first = second = NULL;
    
    Node* curr = root;
    
    stack <Node*> st;
    
    while(!st.empty() ||  root != NULL)
    {
        if(root != NULL)
        {
            // visit current node's (root) left subtree
            st.push(root);
            root = root->left;
        }
        else
        {
            // done left subtree of current node
            root = st.top();
            st.pop();
            
            // compare root.val with root.val if we have one
            if(prev != NULL && root->data < prev->data)
            {
                // incorrect smaller node is always found as prev node
                if(first == NULL) 
                first = prev;
                
                // incorrect larger node is always found as current root node
                second = root;         
            }  
            
            // visit root's right subtree
            prev = root;
            root = root->right;
        }
    }
    
    // fix the BST by swapping values
    int temp = first->data;
    first->data = second->data;
    second->data = temp;
    
    // return address of the original root node
    return curr;
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /* create the incorrect BST*/
    Node *root = new Node(4);
    root->left = new Node(7);
    root->right = new Node(6);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(2);
    
    cout<<"Inorder traversal before : ";
    inorder(root);
    
    root = fixBST(root);
    cout<<endl;
    
    cout<<"Inorder traversal after : ";
    inorder(root);
    
    return 0;
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7
Java Program
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    // function that corrects the BST and returns it's root
    static Node fixBST(Node root)
    {
        Node prev,first,second;
        prev = first = second = null;
        
        Node curr = root;
        
        Stack<Node> st = new Stack<Node>();
        
        while(!st.isEmpty() ||  root != null)
        {
            if(root != null)
            {
                // visit current node's (root) left subtree
                st.push(root);
                root = root.left;
            }
            else
            {
                // done left subtree of current node
                root = st.pop();
                
                // compare root.val with root.val if we have one
                if(prev != null && root.data <= prev.data)
                {
                    // incorrect smaller node is always found as prev node
                    if(first == null) 
                    first = prev;
                    
                    // incorrect larger node is always found as current root node
                    second = root;         
                }  
                
                // visit root's right subtree
                prev = root;
                root = root.right;
            }
        }
        
        // fix the BST by swapping values
        int temp = first.data;
        first.data = second.data;
        second.data = temp;
        
        // return address of the original root node
        return curr;
    }
    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /* create the incorrect BST*/
        Node root = new Node(4);
        root.left = new Node(7);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(2);
        
        System.out.print("Inorder Traversal before : ");
        inorder(root);
        
        root = fixBST(root);
        System.out.println();
        
        System.out.print("Inorder Traversal after : ");
        inorder(root);   
    }
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7

Complexity Analysis for Recover Binary Search Tree

  • Time Complexity : T(n) = O(n)
  • Space Complexity : A(n) = O(n)

Morris Traversal

Approach for Recover Binary Search Tree

The idea is to basically perform inorder Morris traversal of the tree. Morris traversal ensures that traversal takes place in linear time and constant space (not even recursion stack space).

Morris traversal is similar to recursive/iterative traversal, but we need to modify the tree structure during the traversal. before visiting the left tree of a root, we will build a back-edge between a rightmost node in the left tree and the root. So we can go back to the root node after we are done with traversing the left tree.

Then we locate the rightmost node in the left subtree again, cut the back-edge, recover the tree structure, and start visit the right subtree.

The detection of incorrect tree nodes is similar to the recursion/iteration case.

Algorithm

  1. Perform Morris traversal and process each node in inorder fashion.
  2. For every node (except the leftmost node of the tree), keep track of its previous node in prev. The current node being processed is stored in the curr.
  3. If during the traversal, we find a node that violates the BST order. i.e. prev->data > root->data.we store prev into first and root into second.
  4. During further traversal, if we find another node that violates the BST criteria,i.e. prev->data > root->data. but since, the first node had been already assigned a value. so we assign the current node(which violates BST criteria) to second.
  5. After execution of inorder traversal. swap the data of first and second nodes and The tree gets fixed.

Implementation

C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};
 
// function that corrects the BST by performing iterative inorder 
// and returns it's root
Node* fixBST(Node *root)
{
    Node *prev,*first,*second;
    prev = first = second = NULL;
    
    // stores rightmost node in left subtree of root
    Node* rightMost = NULL;
    // stores current node starting with root node 
    Node* curr = root;
    
    while(curr != NULL)
    {
        // for each node, we compare it with prev node as we did in in-order-traversal
        if(prev != NULL && curr->data < prev->data)
        {
            if(first == NULL) 
            first = prev;
            
            second = curr;
        }
        
        if(curr->left != NULL)
        {
            // got left tree, then let's locate its rightmost node in left tree
            rightMost = curr->left;
            // we may have visited the left tree before, and connect the rightmost node with curr node (root node)
            while(rightMost->right != NULL && rightMost->right != curr)
                rightMost = rightMost->right;
            
            if(rightMost->right == curr)
            {
                // if this left tree has been visited before, then we are done with it
                // cut the connection with currNode and start visit curr's right tree
                rightMost->right = NULL;
                prev = curr;
                curr = curr->right;
            }
            else
            {
                // if this left tree has not been visited before, then we create a back edge from rightmost node
                // to curr node, so we can return to the start point after done the left tree
                rightMost->right = curr;
                curr = curr->left;
            }
            
        }
        else
        {
            // no left tree, then just visit its right tree
            prev = curr;
            curr = curr->right;
        }
    }
    
    // swap the values of incorrect nodes
    swap(first->data,second->data);
    return root;
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /* create the incorrect BST*/
    Node *root = new Node(4);
    root->left = new Node(7);
    root->right = new Node(6);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(2);
    
    cout<<"Inorder traversal before : ";
    inorder(root);
    
    root = fixBST(root);
    cout<<endl;
    
    cout<<"Inorder traversal after : ";
    inorder(root);
    
    return 0;
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7
Java Program
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    // function that corrects the BST using morris traversal and returns it's root
    static Node fixBST(Node root)
    {
        Node prev,first,second;
        prev = first = second = null;
        
        // stores rightmost node in left subtree of root
        Node rightMost = null;
        // stores current node starting with root node 
        Node curr = root;
        
        while(curr != null)
        {
            // for each node, we compare it with prev node as we did in in-order-traversal
            if(prev != null && curr.data < prev.data)
            {
                if(first == null) 
                first = prev;
                
                second = curr;
            }
            
            if(curr.left != null)
            {
                // got left tree, then let's locate its rightmost node in left tree
                rightMost = curr.left;
                // we may have visited the left tree before, and connect the rightmost node with curr node (root node)
                while(rightMost.right != null && rightMost.right != curr)
                    rightMost = rightMost.right;
                
                if(rightMost.right == curr)
                {
                    // if this left tree has been visited before, then we are done with it
                    // cut the connection with currNode and start visit curr's right tree
                    rightMost.right = null;
                    prev = curr;
                    curr = curr.right;
                }
                else
                {
                    // if this left tree has not been visited before, then we create a back edge from rightmost node
                    // to curr node, so we can return to the start point after done the left tree
                    rightMost.right = curr;
                    curr = curr.left;
                }
                
            }
            else
            {
                // no left tree, then just visit its right tree
                prev = curr;
                curr = curr.right;
            }
        }
        
        // swap the values of incorrect nodes
        int temp = first.data;
        first.data = second.data;
        second.data = temp;
        
        return root;
    }
    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /* create the incorrect BST*/
        Node root = new Node(4);
        root.left = new Node(7);
        root.right = new Node(6);
        root.left.left = new Node(1);
        root.left.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(2);
        
        System.out.print("Inorder Traversal before : ");
        inorder(root);
        
        // fixing the BST
        root = fixBST(root);
        System.out.println();
        
        System.out.print("Inorder Traversal after : ");
        inorder(root);   
    }
}
Inorder Traversal before : 1 7 3 4 5 6 2 
Inorder Traversal after : 1 2 3 4 5 6 7

Complexity Analysis for Recover Binary Search Tree

  1. Time Complexity : T(n) = O(n)
  2. Space Complexity : A(n) = O(1), nor data structure neither recursion stack space used.

References

Translate »