BST search, insert, and delete operations typically run in time O(d). What is d?

The depth of the relevant node in the tree
  • The number of divisions at each level
  • The number of entries in each node
  • The number of nodes in the tree
  • The total number of entries in all the nodes of the tree

Think about a given insert or search operation.

How many nodes get looked at?

The operation moves down the tree, looking at a node at each level that it visits.

So the total work is the number of nodes that it visits, which is the same as the depth of the last node.