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

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
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
85,317 users