The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
154 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)
in Programming by (75 points) | 154 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).

by (447 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,896 questions
55,153 answers
190,576 comments
85,317 users