Binary tree complexities

Question

I would like to know some complexities of binary search tree.

I can't find complete information. I want to know complexities for the following operations on a binary search tree

to add/insert an element
to remove an element
to find an element (as I know this one is O(log(n)) )

it depends on your algorithm, it has not much to do with the data structure. — m4573r, Mar 23 '13 at 12:36
Binary trees in general? Or binary search trees? Or some specific self-balancing BST? — , Mar 23 '13 at 12:36
Everything about [Binary Trees](http://en.wikipedia.org/wiki/Binary_tree) in Wiki. — masoud, Mar 23 '13 at 12:37
easy explanation: http://stackoverflow.com/a/13093274/550393 — 2cupsOfTech, Feb 22 '16 at 17:02

md5 · Accepted Answer · 2013-03-23T12:44:57.753

10

Insertion, deletion and searching in a binary search tree are:

O(N) in the worst case;
O(log(N)) in the average case.

edited Mar 23 '13 at 12:44

answered Mar 23 '13 at 12:39

md5

23,373
3
44
93

Apurv · Answer 2 · 2017-02-10T05:22:37.403

7

If you have balanced binary tree, all three complexities will be of O(log(N)). If you are not balancing the tree, it could be O(N).

edited Feb 10 '17 at 05:22

answered Mar 23 '13 at 13:00

Apurv

17,116
8
51
67

SChepurin · Answer 3 · 2013-03-23T13:24:34.543

0

Search is effective. But unbalanced structure (which is often the case) can lead to O(N) for search/insert/remove operations. That is why binary heap or other kind of balanced trees are preferred with O(log n). .

edited Mar 23 '13 at 13:24

answered Mar 23 '13 at 13:18

SChepurin

1,814
25
17

Binary tree complexities

3 Answers3