bst.definition
bst.descriptionPart1
bst.descriptionPart2
bst.keyPointsTitle
- bst.keyPoint1
- bst.keyPoint2
- bst.keyPoint3
- bst.keyPoint4
bst.exampleTitle
bst.exampleCaption
bst.syntaxTitle
// Java
class Node {
int value;
Node left, right;
Node(int value) {
this.value = value;
}
}
class BST {
Node root;
void insert(int value) {
root = insertRec(root, value);
}
Node insertRec(Node node, int value) {
if (node == null) return new Node(value);
if (value < node.value)
node.left = insertRec(node.left, value);
else
node.right = insertRec(node.right, value);
return node;
}
}# Python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = Node(value)
else:
self._insert(self.root, value)
def _insert(self, node, value):
if value < node.value:
if node.left: self._insert(node.left, value)
else: node.left = Node(value)
else:
if node.right: self._insert(node.right, value)
else: node.right = Node(value)// C++
struct Node {
int value;
Node *left, *right;
Node(int v) : value(v), left(nullptr), right(nullptr) {}
};
class BST {
public:
Node* root = nullptr;
Node* insert(Node* node, int value) {
if (!node) return new Node(value);
if (value < node->value)
node->left = insert(node->left, value);
else
node->right = insert(node->right, value);
return node;
}
void insert(int value) { root = insert(root, value); }
};// JavaScript
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() { this.root = null; }
insert(value) {
const node = new Node(value);
if (!this.root) { this.root = node; return; }
let current = this.root;
while (true) {
if (value < current.value) {
if (!current.left) { current.left = node; break; }
current = current.left;
} else {
if (!current.right) { current.right = node; break; }
current = current.right;
}
}
}
}Interactive Binary Search Tree
Tree is empty. Insert a value to begin.
Note: Left subtree contains smaller values, right subtree contains larger or equal values. Delete uses inorder predecessor (max of left subtree) for nodes with two children.
enhanced.realWorldExamples.title
Databases use BST variants for range queries and sorting.
Why? Maintains sorted order while allowing efficient operations.
File systems use tree structures for organizing files.
Why? Hierarchical organization with efficient search.
Time Complexity
| Operation | Average Case | Worst Case | Description |
|---|---|---|---|
| Insert | O(log n) | O(n) | Traverse down the tree to find insertion point |
| Search | O(log n) | O(n) | Binary search: compare and go left or right |
| Delete | O(log n) | O(n) | Find node, then handle 0/1/2 children cases |
| Min/Max | O(log n) | O(n) | Traverse to leftmost/rightmost node |
| Inorder Traversal | O(n) | O(n) | Visit all nodes in sorted order |
Average case: Assumes a balanced tree where each level roughly halves the search space.
Worst case: Occurs when tree degenerates into a linked list (e.g., inserting sorted values).
Space complexity: O(n) for storing n nodes, O(h) for recursive operations where h is tree height.
enhanced.complexityAnalysis.title
enhanced.complexityAnalysis.mathematicalTitle
In a balanced BST, each comparison eliminates half the remaining nodes. After k comparisons, n/2^k nodes remain. When n/2^k = 1, k = log₂(n).
🟢Best Case
O(1) when target is at root. O(log n) for balanced tree operations.
🟡Average Case
O(log n) for search, insert, delete in a reasonably balanced tree.
🔴Worst Case
O(n) when tree degenerates into a linked list (all nodes on one side).
💾Space Complexity
O(n) for n nodes. Each node stores data plus two child pointers.