Posts

Showing posts from December, 2022

Recover Binary Search Tree || Solution in C++ || Constant space

 Recover Binary Search Tree We are given a tree such that exactly two values are swapped by mistake. We have to make it a Binary Search Tree by correcting that mistake. Approach 1: We know that the in-order traversal of the Binary Search Tree is always sorted. So we will store the inorder traversal of the given Binary Search Tree in a vector and find the two nodes which are causing the problem and swap them. We will traverse the vector and find the element (the first node causing the problem, say t) whose value is greater than the value of the next node. We will also store the next node (say r). Now r need not be the element so we will traverse the remaining nodes. If any node having a value lesser than the value of r is found then update r to this node. finally, swap the values of t and r.     Time Complexity:          O(n): for traversing the tree,          O(n): for traversing the vector        ...