Insert into a binary tree

Computer Science Level 3

Which of the following represents the time complexity of inserting an element into a binary search tree of $n$ nodes, with the tightest upper bound?

O(n\log n)

O(n)

O(\log n)

O(1)

1 solution

Christopher Boo
May 15, 2016

We know that the time complexity of inserting an element into a binary search tree depends on its height. If the tree forms a chain (a vertical line, with only one leaf), then worst case is you need to traverse the entire chain until the leaf to insert an element. There are $n$ nodes in the chain, hence $O(n)$ .

Insert into a binary tree

1 solution

0 pending reports