Fear_Is_An_Illusion's blog

best method to convert binary tree to binary search tree ?
By Fear_Is_An_Illusion, 9 years ago, In English

Can anyone say the most time efficient method ?. Thanks and sorry if it is easy question.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Should it be in-place? If not, you could create another tree and, while iterating through the binary tree, add nodes to the BST following the rules. Looks like O(n^2) in worst case (when you iterate through an ordered binary tree) and O(nlogn) in best case (when BST is balanced and adding takes logarithmic time).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think he meant in-place because otherwise it's already trivial.

    → Reply