DSA — Non-Linear DS
Binary Search Tree
Binary tree where left < parent < right. O(log n) average search, insert, delete.
O(log n)Search
O(log n)Insert
O(log n)Delete
BSTProperty
BalancedO(log n)
// BINARY SEARCH TREE
Use Insert/Search buttons
How It Works
Code
Complexity
Quiz
Practice
01
Insert Rule
Values less than node go left, greater go right.
if val < node.val: go left
02
Search
Follow left/right until found or null — O(log n) avg.
while node: compare and move
03
Inorder = Sorted
Left→Root→Right gives sorted sequence.
04
Balance Matters
Worst case O(n) if tree is skewed (sorted input).
Python — BST Insert & Search
class BST: def insert(self, root, val): if not root: return Node(val) if val < root.val: root.left = self.insert(root.left, val) elif val > root.val: root.right = self.insert(root.right, val) return root def search(self, root, val): if not root or root.val == val: return root if val < root.val: return self.search(root.left, val) return self.search(root.right, val)
O(log n)
Search/Insert
Balanced tree — height = log n
O(n)
Worst Case
Skewed tree e.g. sorted input
Inorder
Sorted Output
Left→Root→Right = sorted
O(n)
Space
One node per element
What traversal of a BST gives sorted output?
Progress0 / 13 solved
13 problems · 10 PBC · 3 Startup