The question is tricky as you need to veify if interviewer is talking about balanced or unbalanced search tree.

The best case performance for a balanced binary search tree during search operations is O(log N), so is the average and worst case.

Unbalanced binary search trees are different story and performance relies on the order in which data inserted or deleted. The worst case of an unbalanced tree is O(N) and the best case is O(log N).

Here is the general operation of insert on BST, but if the tree is balanced it might be required to rebalance it after new node is added:

private void AddNodeBST(int key, Node tree)
{
if (key == tree.Key) return; // Smaller numbers go to the left
if (key < tree.Key)
{
if (tree.Left == null)
{
tree.Left= new BSTNode();
tree.Left.Key = key;
} else
{
// use recursion to follow the tree
AddNodeBST(key, tree.Left);
}
}
// Larger and equal numbers go to the right
else
if (tree.Right == null) {
tree.Right = new BSTNode();
tree.Right.Key = key; }
else {
// use recursion to follow the tree
AddNodeBST(key, tree.Right); } }







Answers and Comments