Trees - Recover Binary Search Tree

Two nodes of the BST are swapped by mistake. Recover the tree without changing its structure.

Input: root=[1,3,null,null,2] → Output: [3,1,null,null,2]

Input: root=[3,1,4,null,null,2] → Output: [2,1,4,null,null,3]

Inorder traversal of BST should give sorted sequence. Find two nodes where order is violated: first is the node where nums[i] > nums[i+1] for the first time, second is the smaller of the violating pair or the last violation.

Do inorder traversal, tracking prev node.
When prev.val > cur.val: if first==null, first=prev; second=cur.
After traversal, swap first.val and second.val.

class Solution { TreeNode first, second, prev; public void recoverTree(TreeNode root) { inorder(root); int tmp = first.val; first.val = second.val; second.val = tmp; } private void inorder(TreeNode node) { if (node == null) return; inorder(node.left); if (prev != null && prev.val > node.val) { if (first == null) first = prev; second = node; } prev = node; inorder(node.right); } }

Time Complexity: O(N)
Space Complexity: O(H)