I tried different approaches but unable to figure out the output format
How to approach this question for recover binary search Tree
hello @nitinchoudhary260
- Construct inorder traversal of the tree. It should be an almost sorted list where only two elements are swapped.
- Identify two swapped elements x and y in an almost sorted array in linear time.
- Traverse the tree again. Change value x to y and value y to x.
What changes I need to make in the program for displaying the correct output
https://ide.codingblocks.com/s/475772 My code is not giving correct output what should I change in it
pls reread the input format, in input are given preorder traversal, but the method that u r using for construction is of level order.
pls correct that and then try again
In the input Example It is given only the tree values
still its in preorder
We have to give input in inorder than
…
not in inorder.
it is given in preorder. so u need to change ur build tree function as well.
u need to perform preorder traversaal and construct tree recursively
Okk Thanks got It now
ur recover tree logic is correct.
the issue is only with input in building tree, In input format they are saying something else but in sample input they are giving something else. pls try to submit ur code on some other platform it will work.
@nitinchoudhary260
some clarifications regarding input->
a) u will not be given size
b) only preorder traversal is given where -1 indicates no node.
c) the method for constrcuting tree from preorder is differnt than what u are using in ur code
pls refer build tree function of this code ->
Thanks for resolving the issue
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.