Fixing Two swapped nodes of a BST

Summary

The problem involves fixing two swapped nodes in a Binary Search Tree (BST). The goal is to restore the original order of the tree by swapping back the incorrect nodes. This problem requires understanding of binary search trees and their traversal methods.

Detailed Explanation

To solve this problem, we can start by performing an inorder traversal of the BST to get all the node values in ascending order. Then, we compare each pair of adjacent nodes to find the swapped nodes. Once we've identified the two swapped nodes, we need to restore the original order by swapping them back.

Here's a step-by-step breakdown of the solution:

Perform an inorder traversal of the BST to get all node values in ascending order.
Compare each pair of adjacent nodes to find the swapped nodes. The swapped nodes will have the same value but different parent-child relationships than their original counterparts.
Once we've identified the two swapped nodes, swap them back to restore the original order.

Here's an ASCII art diagram illustrating the problem:

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

In this example, the nodes with values 3 and 5 are swapped. To fix this, we would swap them back to restore the original order.

Time complexity: O(n), where n is the number of nodes in the BST. Space complexity: O(1) as we only use a constant amount of space for our algorithm.

Optimized Solutions

Java

public class FixSwappedNodes { public static void fixSwappedNodes(Node root) { if (root == null) return; List<Integer> inorder = new ArrayList<>(); inorder(root, inorder); int prev = Integer.MIN_VALUE; for (int i = 0; i < inorder.size() - 1; i++) { if (inorder.get(i) > inorder.get(i + 1)) { // Swap nodes int temp = inorder.set(i, inorder.get(i + 1)); inorder.set(i + 1, temp); return; } } } private static void inorder(Node node, List<Integer> inorder) { if (node == null) return; inorder(node.left, inorder); inorder.add(node.val); inorder(node.right, inorder); } }