Binary tree

Question

What is the best Big-O runtime for inserting an element into a binary tree?

Answer 1

The best case will be for balanced binary search tree, O(log n).

Inserting an element takes time proportinal to  the tree height.

Comments

Best case insertion time will be O(1) (new node's place is the appropriate place i.e. leaf node itself and requires no changes)

Worst case insertion time in BINARY tree can be O(n) [in case it is skewed]

Worst case insertion time in BALANCED BINARY tree will be O(log n) as correctly said by you.

Please correct me if there are any errors!

---

For Balanced Binary Search Tree: Best, Average and Worst case is O(log n).

You are right, you could say that the Best case is O(1).

Answer 2

It depends on data structure used to represent a binary tree.

If array is used then inserting will take O(1), just insert at the last position in an array.

If standard structure is made then it takes O(logn) time in best case if tree is balanced but if it left or right skewed then it takes O(n) if we want to insert in leaf node, if we try to insert at root then it will take O(1) in case of skewed binary tree.