I am very confused by the description of this problem: Recover Binary Search Tree

  • 6

    Two elements of a binary search tree (BST) are swapped by mistake.
    Recover the tree without changing its structure.

    I saw most of the algorithm find the two nodes first, then change their value;
    The problem is that "Two elements of a binary search tree" should mean that the two nodes are swapped by mistake. We need to swap the two nodes, not just the value.
    In practice, the tree nodes may contain other information and swapping only the values will make another mistake, instead of fixing it.

  • 4

    This is definitely a good point to talk about in a real interview. For implementation, you can practice both ways. It's just that swapping actual nodes are a bit harder to do since you need to changing three pointers for every node swapped.

  • 1

    I agree. The question needs more clarification. Swapping two nodes to me means the subTree of the two nodes are swapped as well. That's a different story.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.