Recover a Binary Search Tree if positions of two nodes are swapped.

Two elements of a binary search tree (BST) are swapped by mistake. Restore the BST structure without changing positions of nodes which are correctly placed.

Please try solving this problem before jumping on the solution

Click to learn

Subscribe for more updates


The main idea that we are going to use is that in-order traversal array for a BST would be a sorted array.
If this order is not maintained, then we know that the nodes are not correctly placed.
Please see the pseudo-code below to understand the algorithm.

1. Initialize firstStartPoint = null, lastEndPoint = null, previous_node = null
2. Visit all nodes of a tree in in-order fashion. Keep track of previously visited node.
3. At each node that is being visited,
    if value of previously visited node > current node
        if(firstStartPoint == null)
            firstStartPoint = previous_node
         lastEndPoint = current_node;
4. After all nodes are visited :swap firstStartPoint with lastEndPoint     

Please check out the video for an illustrative explanation.

Algorithm Visualization

Code Snippet

package com.ideserve.nilesh.questions;

public class RecoverBST
   static class TreeNode
		TreeNode left;
		TreeNode right;
		int val;
		public TreeNode(int x)
			this.val = x;

	TreeNode firstStartPoint, lastEndPoint;
    TreeNode prevNode;

    public void findSegments(TreeNode root) 
        if (root == null) return;
        findSegments (root.left);
        if (prevNode != null) 
            if (prevNode.val   >  root.val) 
                if (firstStartPoint == null)
                	firstStartPoint = prevNode;
                lastEndPoint = root;
        prevNode = root;
        findSegments (root.right);   
   public void recoverTree(TreeNode root) 
       int x = firstStartPoint.val;
       firstStartPoint.val = lastEndPoint.val;
       lastEndPoint.val = x;

   public void printInOrder(TreeNode root)
	   if (root == null) return;
   public static void main(String[] args)
	   TreeNode root = new TreeNode(10);
	   TreeNode n1   = new TreeNode(15);
	   TreeNode n2   = new TreeNode(5);
	   TreeNode n3   = new TreeNode(4);
	   TreeNode n4   = new TreeNode(7);
	   TreeNode n5   = new TreeNode(14);
	   TreeNode n6   = new TreeNode(17);
	   root.left  = n1;
	   root.right = n2;
	   n1.left  = n3;
	   n1.right = n4;
	   n2.left  = n5;
	   n2.right = n6;
	   RecoverBST solution = new RecoverBST();
	   System.out.println("In-Order traversal of BST before recovery: ");

	   System.out.println("In-Order traversal of BST after recovery: ");

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More