Notes › DSA
Binary Trees and BST
A tree is a hierarchy of nodes connected by edges, with no cycles. A binary tree gives each node at most two children: left and right.
1 ← root (depth 0)
/ \
2 3 ← depth 1
/ \ \
4 5 6 ← leaves (no children)
Terms
| Term | Meaning |
|---|---|
| Root | top node, no parent |
| Leaf | node with no children |
| Depth of a node | edges from the root to it |
| Height of a tree | edges (or nodes, define it!) on the longest root-to-leaf path |
| Full binary tree | every node has 0 or 2 children |
| Complete binary tree | all levels full except maybe the last, filled left to right (heaps) |
| Perfect binary tree | all levels completely full: 2ʰ⁺¹ − 1 nodes |
| Balanced | heights of left and right subtrees differ by at most 1 everywhere → height O(log n) |
struct TreeNode {
int val; TreeNode *left, *right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
The four traversals
| Traversal | Order | For the tree above | Typical use |
|---|---|---|---|
| Preorder | Root, Left, Right | 1 2 4 5 3 6 | copy / serialise a tree |
| Inorder | Left, Root, Right | 4 2 5 1 3 6 | sorted order in a BST |
| Postorder | Left, Right, Root | 4 5 2 6 3 1 | delete a tree, compute heights |
| Level order | level by level (BFS) | 1 2 3 4 5 6 | shortest depth, views, zigzag |
void inorder(TreeNode* n, vector<int>& out) {
if (!n) return;
inorder(n->left, out);
out.push_back(n->val);
inorder(n->right, out);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q; q.push(root);
while (!q.empty()) {
int sz = q.size(); // nodes in this level
res.push_back({});
while (sz--) {
TreeNode* n = q.front(); q.pop();
res.back().push_back(n->val);
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
}
return res;
}
See them animated: inorder, preorder, postorder, level order.
The key recursive question
Most tree problems are solved by asking: "What does each child need to return to its parent?"
int height(TreeNode* n) { // nodes on the longest path
if (!n) return 0;
return 1 + max(height(n->left), height(n->right));
}
int best = 0; // diameter: longest path between any two nodes (edges)
int depth(TreeNode* n) {
if (!n) return 0;
int l = depth(n->left), r = depth(n->right);
best = max(best, l + r); // path through this node
return 1 + max(l, r); // what the parent needs
}
Lowest common ancestor (binary tree)
TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* l = lca(root->left, p, q);
TreeNode* r = lca(root->right, p, q);
if (l && r) return root; // p and q are on different sides
return l ? l : r;
}
Binary Search Tree (BST)
For every node: all values in the left subtree < node < all values in the right subtree. Inorder traversal of a BST gives sorted values.
TreeNode* insert(TreeNode* root, int v) {
if (!root) return new TreeNode(v);
if (v < root->val) root->left = insert(root->left, v);
else root->right = insert(root->right, v);
return root;
}
bool search(TreeNode* root, int v) {
while (root) {
if (v == root->val) return true;
root = v < root->val ? root->left : root->right;
}
return false;
}
Delete has three cases: a leaf (remove it), one child (replace it with the child), two children (copy the inorder successor — the smallest node of the right subtree — and delete that instead).
| Operation | Balanced BST | Skewed BST (like a linked list) |
|---|---|---|
| Search / insert / delete | O(log n) | O(n) |
Self-balancing BSTs (AVL, Red-Black) keep the height O(log n) — C++ set/map and Java TreeMap are Red-Black trees.
Validate a BST: pass an allowed (min, max) range down the recursion — checking only a node against its children is a classic mistake.
Classic problems
| Problem | Idea |
|---|---|
| Max depth, diameter, balanced tree | postorder: return height |
| Same tree / symmetric tree | compare two trees in parallel |
| Level order, zigzag, right side view | BFS level by level |
| Path sum / max path sum | return the best downward path |
| LCA of binary tree / BST | recursion (BST: use values) |
| Validate BST, kth smallest in BST | inorder / ranges |
| Build tree from preorder + inorder | root from preorder, split by inorder |
| Serialize / deserialize | preorder with null markers |
Practise in the Trees section.
Interview one-liners
- A tree with n nodes has n − 1 edges.
- Recursion uses O(h) stack space — O(log n) balanced, O(n) skewed.
- Height-balanced does not mean complete; complete does not mean BST.
- BFS needs O(width) memory, DFS needs O(height).