Skip to main content
Computer Science

Return to Question

Big $O$ instead of little $o$.
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91

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

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

for exmapleexample :

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

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

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

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

Source Link
user99038
user99038

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