I'm stuck on this question, a BST is slightly broken only if there is a node with value x in which :

there is atleast one value less than x on its right branch or atleast one value greater than x on its left branch.

for exmaple : 
  

  

                    3
                   / \
                 10   5
                 /\   /\
                8 15 4  7

suggest an algorithm which will fix the tree also it should keep its original shape and same values. at worst case o(n).

I know its possible ot fix it and keep same shape but I can't seem to find the an algorithm that is at worst case o(n).