The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
131 views

What is the time complexity for insertion in binary tree in worst case?

  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n log n)
asked in Programming by (75 points) | 131 views
+2
In the Worst case, it may grow left skew binary tree or right skew binary tree.

So, time complexity will be $O(n)$

1 Answer

+1 vote

Image result for left skewed binary tree

 

For inserting element as the left child of D(either in a left-skewed binary tree or right skewed binary tree), we have to traverse all elements(i.e. A, B, C, D). Therefore, insertion in the binary tree has worst-case complexity of O(n).

answered by (427 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,532 questions
54,123 answers
187,319 comments
71,044 users