Binary Tree: Insert in O(1) time, Delete, and Search

Problem Statement

We want to create a balanced binary tree that supports insertion in O(1) time, deletion, and search operations.

Let’s have the following two constraints on insertion:

• We insert a node in the next level if the current level is complete.
• We create a right child if the left child is already present.

With these constraints, we guarantee that the binary tree is a complete binary tree that could be a perfect binary tree, given that we insert the right amount of nodes in the tree. Also, the binary tree will be a balanced binary tree.

Representation

First of all, we need to represent the binary tree. From the definition, a tree is a collection of nodes. A node consists of a value and references to its child nodes. We can represent the node as:

Node =>
   Value
   Node Left
   Node Right

We can represent the tree as:

Tree =>
    Node Root

The outside world need not know the internals of the node and the tree. We will provide the following interfaces for the outside world:

tree.insert(value)
tree.delete(value)
tree.search(value)

Insertion

Suppose we are inserting numbers from 1 to 11: