fixing a slightly broken BST tree

Question

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

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

for example :

                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)$, where $n$ is the number of values.

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

Answer 1

The problem must have said that there is at most one node such that, if its value is $x$, "there is at least one value less than $x$ on its right branch or at least one value greater than $x$ on its left branch". Otherwise, any binary tree could be "a slightly broken BST tree". It is not possible to construct a BST in $O(n)$ from random $n$ values in general.

Here is the explanation for an $O(n)$ algorithm.

First, as you should have observed, we can concentrate on the subtree with the broken node as the root. Let us assume that the root of the tree is the broken node.

Perform in-order traversal on the left subtree to list all values in the left subtree. Perform in-order traversal on the right subtree to list all values in the right subtree. Merge these two ordered list. Insert the value of broken node. Now we get all values in an ordered list.

Now traverse the whole tree in-order. In other usual situations we will print its value when we visit a node. Instead, we will replace the values of nodes using the successive values in that ordered list when we visit the nodes.

It is clear that each step above takes $O(n)$ time.