https://leetcode.com/problems/recover-binary-search-tree

If we want to traverse our tree and do not use any additional memory, than as far as I know, Morris traversal is the only way how to do it.

For more details about Morris traversal, you can look at oficial solution of problem 94: Binary Tree Inorder Traversal: https://leetcode.com/problems/binary-tree-inorder-traversal/solution/.

Also, here we need to use variation of traversal, which keep the original structure of tree.

Let us use this traversal and use node is current node we are in and cands are candidates for our swapped nodes. We will look at oddities in inorder traversal: in BST all numbers will always increase. So, if in inorder traversal some value is less than previous, we need to keep and eye on this node. There can be two main cases:

  1. We have 1, 2, 3, 4, 5 and swapped nodes are adjacent, for example 1, 2, 4, 3, 5. In this case, we have only one oddity: 4 and 3: and we save them to our cands list. And we need to change values for the first and for the last nodes in our cands.
  2. We have 1, 2, 3, 4, 5 and swapped nodes are not adjacent, for example 1, 2, 5, 4, 3. In this case we have two oddities: 5 and 4; 4 and 3. In this case we again need to swap the first and the last nodes.

So, in both cases it is enough to run cands[0].val, cands[-1].val = cands[-1].val, cands[0].val to swap our nodes.

Complexity: time complexity is O(n): because we basically do Morris traverasal plus some additional O(n) operations. Space complexity is O(1), becauswe we again do Morris traversal and also we have node and cands, where cands can have maximum size 4.

class Solution:
    def recoverTree(self, root):
        cur, node, cands = root, TreeNode(-float("inf")), []
        while cur:
            if cur.left:
                pre = cur.left
                while pre.right and pre.right != cur:
                    pre = pre.right
                if not pre.right:
                    pre.right = cur
                    cur = cur.left
                else:
                    pre.right = None
                    if cur.val < node.val:
                        cands += [node, cur]
                    node = cur
                    cur = cur.right
            else:
                if cur.val < node.val:
                    cands += [node, cur]
                node = cur
                cur = cur.right
            
        cands[0].val, cands[-1].val = cands[-1].val, cands[0].val

If you like the solution, you can upvote it on leetcode discussion section: Problem 0099