What is a Binary Search Tree (BST)? What are its properties?

Difficulty: 5/10

insertion, deletion, balancing

Binary Search Tree

A Binary Search Tree is a binary tree that maintains an ordering invariant. For a node, values in the left subtree are smaller and values in the right subtree are larger, assuming the implementation does not allow duplicates. This ordering enables efficient search, insertion, and deletion when the tree remains balanced.

javascript

1
Left subtree contains smaller values.
2
Right subtree contains larger values.
3
Inorder traversal produces sorted order.
4
Search, insertion, and deletion are O(h), where h is tree height.
5
For a balanced BST, these operations are typically O(log n).
6
For a highly skewed BST, they can degrade to O(n).

Scenario Questions

0-2 years experience

Follow-up Questions