Recover Binary Search Tree

This page explains Java solution to problem Recover Binary Search Tree using In Order Traversal of Tree data structure.

Problem Statement

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

Recover the tree without changing its structure.

Input: [1,3,null,null,2]
   1
  /
 3
  \
   2

Output: [3,1,null,null,2]
   3
  /
 1
  \
   2

Input: [3,1,4,null,null,2]
  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]
  2
 / \
1   4
   /
  3

Solution

package com.vc.hard;

/**
 * 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 RecoverBinarySearchTree {
    private TreeNode prev = null, small = null, large = null;

    public void recoverTree(TreeNode root) {
        helper(root);
        int temp = small.val;
        small.val = large.val;
        large.val = temp;
    }

    private void helper(TreeNode root) {
        if(root != null) {
            helper(root.left);
            if(prev != null && prev.val > root.val) {
                if(large == null) large = prev;
                small = root;
            }
            prev = root;
            helper(root.right);
        }
    }
}

Time Complexity

O(N) Where
N is total number of elements in an input Tree

Space Complexity

O(1)