Morris traversal to solve Leetcode Q-99

November 9, 2019

Q-99: recover BST tree with two wrongly nodes

Note: This solution solved the problem in constant space, without any stack usage.

# Morris 
def recover_tree(root)
  x = y = pre = nil
  while root
    if root.left
      predsr = root.left
      predsr = predsr.right while predsr.right && predsr.right != root
      if !predsr.right
        predsr.right = root
        root = root.left
      else
        if pre && root.val < pre.val
          y = root
          x ||= pre
        end
        pre = root
        predsr.right = nil
        root = root.right
      end
    else
      if pre && root.val < pre.val
        y = root
        x ||= pre
      end
      pre = root
      root = root.right
    end
  end
  x.val, y.val = y.val, x.val
end