Binary Search Tree

A binary search tree (BST) is a binary tree whose nodes are arranged according to an ordering rule, allowing efficient ordered search and updates when the tree remains reasonably balanced. For a node, values in the left subtree are smaller and values in the right subtree are larger under the chosen ordering convention.

A BST has at most two children per node. Its defining property is recursive: every value in a node's left subtree belongs before the node's value, and every value in its right subtree belongs after it. The exact treatment of duplicate values must be defined by the implementation.

Searching starts at the root and compares the target with the current value. A smaller target moves left; a larger target moves right; equality means the target has been found. Each comparison therefore eliminates one subtree from consideration.

Insertion follows the same search path until an appropriate empty child position is found. Deletion is more involved: a leaf can be removed directly, a node with one child can be replaced by that child, and a node with two children is commonly replaced using its inorder successor or predecessor.

An inorder traversal of a BST visits values in sorted order, assuming the ordering invariant is maintained. Search, insertion, and deletion take O(h) time, where h is the tree height; this is O(log n) for a balanced tree but can become O(n) when the tree is highly skewed.

Key points

• Each node has at most two children.
• The left subtree contains smaller values and the right subtree contains larger values, according to the chosen duplicate policy.
• Search, insertion, and deletion depend on tree height h.
• Inorder traversal produces sorted values when the BST invariant holds.
• A skewed BST can degrade to linear-time operations.

Interview questions

What is a binary search tree, and what property makes it useful?

A BST is a binary tree with an ordering invariant. Values that compare smaller than a node are placed in its left subtree, while larger values go in its right subtree, subject to the duplicate policy. This lets a search choose one child at each comparison instead of examining both subtrees. The same property supports ordered insertion and traversal.

What is the time complexity of searching a BST?

Searching takes O(h), where h is the height of the tree. In a balanced tree, h is O(log n), giving logarithmic search time. In the worst case, a skewed tree has height O(n), so search becomes O(n). The complexity therefore depends on the tree's shape.

How do you insert a value into a BST?

Start at the root and compare the new value with the current node. Move left when it belongs before the current value and right when it belongs after it. Continue until the required child reference is empty, then attach the new node there. Duplicate handling must follow the tree's defined policy.

How do you delete a node from a BST?

Deletion has three structural cases. A leaf can simply be removed, while a node with one child can be replaced by that child. For a node with two children, a common approach is to replace its value with the inorder successor, then delete that successor from its original position. The replacement must preserve the BST invariant.

Why can a BST have O(n) operations despite binary search being O(log n)?

Binary search is logarithmic when each step roughly halves the remaining search space. A BST only guarantees that one subtree can be discarded; it does not by itself guarantee that the two subtrees are similarly sized. If values are inserted in an unfavorable order, the tree can become a chain with height n minus one. Operations then take O(n) in the worst case.