fixing a slightly broken BST tree

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)$$.

• Can you double check whether the original problem says it is a balanced BST? Does it say big $O$-notation $O(n)$ or little $o$-notation $o(n)$? Or is that broken node given? – John L. Jan 14 '19 at 19:53
• Its big O nation , the given tree is an example for what is a slightly broken bst, as for the balanced it doesnt say if its balanced or not. – Foghunt Jan 14 '19 at 21:22

1 Answer

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.

• Yes it did say at most there is one node. Thank you for the answer. – Foghunt Jan 15 '19 at 6:06