Problem Statement
What is a Binary Search Tree? Explain its properties and the time complexity of its operations.
Explanation
A Binary Search Tree is a binary tree with a specific ordering property: for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value. This property makes BSTs efficient for search, insertion, and deletion operations.
The key properties of a BST are that each node has at most two children called left and right, the left subtree of a node contains only values less than the node's value, the right subtree contains only values greater than the node's value, and both left and right subtrees must also be valid BSTs. This recursive property ensures the tree maintains its ordering throughout.
Search operation starts at root and compares the target value with current node. If equal, we found the value. If target is less, search left subtree. If target is greater, search right subtree. Average time complexity is O of log n for balanced trees, worst case is O of n for skewed trees.
Insertion follows the same path as search to find the correct position, then inserts the new node as a leaf. This maintains the BST property. Time complexity is O of log n average case, O of n worst case.
Deletion has three cases. If the node has no children, simply remove it. If the node has one child, replace it with its child. If the node has two children, find the in-order successor which is the minimum value in right subtree or in-order predecessor which is maximum in left subtree, copy its value to the node being deleted, then delete the successor or predecessor. Time complexity is O of log n average, O of n worst case.
The performance of BST operations depends heavily on tree balance. In the best case with a balanced tree, height is log n and operations are efficient. In the worst case with a skewed tree where nodes form a chain, height is n and operations degrade to linear time. This is why self-balancing trees like AVL and Red-Black trees are used to guarantee logarithmic performance.
