Leetcode Problem 99. Recover Binary Search Tree

99. Recover Binary Search Tree

Leetcode Solutions

Morris Inorder Traversal

  1. Initialize two pointers, first and second, to None. These will be used to track the two nodes that need to be swapped.
  2. Initialize a pointer pred (predecessor) to None to keep track of the previous node in the inorder traversal.
  3. Start with the root node and iterate while the current node is not None.
  4. If the current node has a left child, find the rightmost node in the left subtree (the predecessor).
  5. If the predecessor's right child is None, set it to the current node and move to the left child of the current node.
  6. If the predecessor's right child is the current node, it means we have already visited the left subtree. Set the predecessor's right child to None and check if the current node is out of order with the pred node. If it is, update first and second.
  7. Move to the right child of the current node.
  8. After the traversal, swap the values of first and second.
UML Thumbnail

Recursive Inorder Traversal

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...