Break out BFS recursion

Introduction

Today I solved the following problem.

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

public class T099RecoverBST {
	private TreeNode first;
	private TreeNode second;
	
	private TreeNode smaller =  new TreeNode(Integer.MIN_VALUE);
	private TreeNode bigger =  new TreeNode(Integer.MAX_VALUE);
	
	
	public void recoverTree(TreeNode root) {
		helperTofindFirst(root);
		helperTofindSecond(root);
		swap(first, second);
	}
	
	private void swap(TreeNode first, TreeNode second) {
		int temp = first.val;
		first.val = second.val;
		second.val = temp;
	}
	
	private void helperTofindFirst(TreeNode root) {
		if(root == null)
			return;
		helperTofindFirst(root.left);
		
		if(first != null)
			return;
		if(smaller.val >= root.val)
			first = smaller;
		
		smaller = root;
		helperTofindFirst(root.right);
	}
	
	
	private void helperTofindSecond(TreeNode root) {
		if(root == null)
			return;
		helperTofindSecond(root.right);
		
		if(second != null)
			return;
		if(bigger.val <= root.val)
			second = bigger;
		
		bigger = root;
		helperTofindSecond(root.left);
	}
}

Analysis

Here, we need to break out the recursion when we find the first or second node. However, the following code doesn’t break out correctly

	private void helperTofindSecond(TreeNode root) {
		if(second != null || root == null)
			return;
		helperTofindSecond(root.right);
		
		if(bigger.val <= root.val)
			second = bigger;
		
		bigger = root;
		helperTofindSecond(root.left);
	}

We need to use if to check if second is null after the helperTofindSecond(root.right);