Data Structures & Algorithms: Industry Edition
Unit 4: Trees
Binary Trees, BST, Traversals, LCA & Kth Element — with real examples from Nykaa, Linux File System & MongoDB.
🏢 Real Projects | 💻 5 Lab Programs (Python + C) | 📝 25 MCQs | 🎯 3 Interview Questions
Industry Hook — The Real-World Problem First
💄 The Nykaa Problem: 5 Million Products in a Hierarchy
Nykaa, India's largest beauty e-commerce platform, has over 5 million products organized into a deep category hierarchy:
Nykaa
/ | \
Beauty Fashion Wellness
/ \ |
Skincare Makeup Ethnic
/ \
Moisturizer Sunscreen
/ \
Under ₹500 Premium
When a customer searches "moisturizers under ₹500," the system must navigate this tree to reach the correct category — that's tree traversal. When an admin adds a new sub-category, they insert a node — that's tree insertion. When Nykaa needs to find the common category between "Sunscreen" and "Moisturizer," it finds "Skincare" — that's the Lowest Common Ancestor (LCA).
The same tree structure powers your computer's file system (C:\ → Users → Documents), the Linux kernel's VFS, every database index (MongoDB uses B-Trees), and DOM manipulation in every web browser.
This is exactly the problem trees solve. Let's understand how.
Concept Explanation — Theory, Earned
2.1 Binary Trees
Layer 1 — Intuition
A tree is like a family tree — one ancestor (root) at the top, and each person has at most two children (in a binary tree). You can't go "up" without following the parent pointer. A binary tree is the special case where every node has at most 2 children: left and right.
Layer 2 — Visual
Binary Tree Structure
1 ← Root (Level 0)
/ \
2 3 ← Level 1
/ \ \
4 5 6 ← Level 2 (Leaves: 4, 5, 6)
Terminology:
Root = 1 (topmost node, no parent)
Leaf = 4, 5, 6 (no children)
Internal = 1, 2, 3 (at least one child)
Height = 2 (longest root-to-leaf path)
Depth(5) = 2 (edges from root to node 5)
Types of Binary Trees
| Type | Property | Example Use |
|---|---|---|
| Full Binary Tree | Every node has 0 or 2 children | Expression trees |
| Complete Binary Tree | All levels filled except possibly the last (filled left-to-right) | Binary heaps |
| Perfect Binary Tree | All internal nodes have 2 children, all leaves at same level | Theoretical ideal |
| Extended Binary Tree | Every node has exactly 0 or 2 children (same as Full) | Huffman coding trees |
Memory Representation
Linked Representation (Most Common)
Each node is a struct/class with 3 fields:
┌──────┬──────┬──────┐
│ left │ data │ right│
└──┬───┴──────┴───┬──┘
↓ ↓
(left child) (right child)
Sequential (Array) Representation
For node at index i:
Left child = 2i + 1
Right child = 2i + 2
Parent = (i - 1) / 2
Index: 0 1 2 3 4 5
Value: [1] [2] [3] [4] [5] [6]
Used for: Binary heaps (complete trees). Wastes space for sparse trees.
2.2 Tree Traversals
The Three Traversal Orders
Tree: 1
/ \
2 3
/ \
4 5
In-order (Left, Root, Right): 4, 2, 5, 1, 3 ← Gives SORTED order for BST!
Pre-order (Root, Left, Right): 1, 2, 4, 5, 3 ← Used to COPY/SERIALIZE a tree
Post-order (Left, Right, Root): 4, 5, 2, 3, 1 ← Used to DELETE a tree safely
In-order traversal of a BST always gives sorted output. This is the BST's superpower. If you insert 50, 30, 70, 20, 40, 60, 80 into a BST and do an in-order traversal, you get: 20, 30, 40, 50, 60, 70, 80. Sorted! This is how databases retrieve records "in order" — they traverse a B-Tree in-order.
2.3 Binary Search Tree (BST)
Layer 1 — Intuition
A BST is like a dictionary organized by first letter. If you're looking for "Mango," you open to the middle. "Mango" > "J"? Go right half. "Mango" < "P"? Go left half. Each decision eliminates half the remaining pages — exactly like binary search, but built into the tree structure itself.
Layer 2 — BST Property
BST Property
For EVERY node:
• All values in LEFT subtree < node's value
• All values in RIGHT subtree > node's value
50
/ \
30 70 ← 30 < 50 < 70 ✓
/ \ / \
20 40 60 80 ← 20 < 30 < 40 ✓, 60 < 70 < 80 ✓
Search for 40:
50 → 40 < 50 → go LEFT
30 → 40 > 30 → go RIGHT
40 → FOUND! (3 comparisons for 7 nodes)
Layer 3 — Complexity Table
| Operation | Average (Balanced) | Worst (Skewed) | Space |
|---|---|---|---|
| Search | O(log n) | O(n) | O(1) iterative / O(h) recursive |
| Insert | O(log n) | O(n) | Same |
| Delete | O(log n) | O(n) | Same |
| In-order traversal | O(n) | O(n) | O(h) stack |
| Find Min/Max | O(log n) | O(n) | O(1) |
If you insert elements [10, 20, 30, 40, 50] into a BST in that order, what does the tree look like? It becomes a right-skewed linked list! Search becomes O(n). This is why the ORDER of insertion matters, and why self-balancing trees (AVL, Red-Black) exist — they guarantee O(log n) regardless of insertion order.