# Untitled

unknown
plain_text
2 months ago
1.8 kB
1
Indexable
Never
class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int val) {
this.val = val;
}
}

public class Main {
TreeNode firstIncorrectNode = null;
TreeNode secondIncorrectNode = null;
TreeNode prevNode = new TreeNode(Integer.MIN_VALUE);

public void recoverTree(TreeNode root) {
// Perform inorder traversal
inorder(root);
// Swap the values of the two incorrectly placed nodes
int temp = firstIncorrectNode.val;
firstIncorrectNode.val = secondIncorrectNode.val;
secondIncorrectNode.val = temp;
}

private void inorder(TreeNode node) {
if (node == null)
return;
inorder(node.left);
// Check for incorrectly placed nodes
if (firstIncorrectNode == null && prevNode.val >= node.val) {
firstIncorrectNode = prevNode;
}
if (firstIncorrectNode != null && prevNode.val >= node.val) {
secondIncorrectNode = node;
}
prevNode = node;
inorder(node.right);
}

public static void main(String[] args) {
// Create a sample binary search tree with incorrect nodes
TreeNode root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.right.left = new TreeNode(2);

Main solution = new Main();
solution.recoverTree(root);

// Print the corrected BST
System.out.println("Inorder Traversal of Recovered BST:");
printInorder(root);
}

// Helper function to print the inorder traversal of a tree
private static void printInorder(TreeNode node) {
if (node == null)
return;
printInorder(node.left);
System.out.print(node.val + " ");
printInorder(node.right);
}
}