Recover BST
Advanced Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Recover BST | Correct BST with two nodes swapped, Binary Tree, Binary Search Tree, Tree Traversal, In-order Traversal, Iteration, Stack, Time Complexity, Space Complexity, Algorithm, Data Structures, Pointer, inorder traversal, binary search tree properties, tree operations, binary search tree, Insertion & Deletion in BST, Recover BST.
Recover BST A Binary Search Tree (BST) is a binary tree where for each node, all values in its left subtree are less than its own value, and all values in its right subtree are greater than its own value. You are given the root of a Binary Search Tree (BST), where exactly two nodes have been swapped by mistake. Your task is to recover the tree without changing its structure (i.e., only by modifying the node values). Input Format: The input consists of the root node of the corrupted BST. Each node has an integer value, a left child pointer, and a right child pointer. Output Format: Return the root of the corrected BST. The correction must be done in place, by swapping the values of the two erroneous nodes. Constraints: The number of nodes in the tree is between 1 and 1000. Node values are integers.