Chapter 21: DSA Trees
DSA Trees – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing pictures, giving many real-life examples, explaining step-by-step, showing code patterns, and most importantly telling you why trees are one of the most important data structures you must master for interviews and real software engineering.
What is a Tree in DSA?
A Tree is a hierarchical, non-linear data structure that represents data in a parent-child relationship.
Main characteristics:
- There is one special node called the root (has no parent)
- Every other node has exactly one parent
- Nodes can have zero or more children
- There are no cycles (you cannot go back to the same node by following child pointers)
- It looks like an upside-down real tree (root at top, leaves at bottom)
Real-life examples where trees are used (very important intuition)
| Real-life situation | Tree structure representation | Node = ? | Children = ? |
|---|---|---|---|
| Company organization chart | CEO → Managers → Team Leads → Employees | Employee | Direct reports |
| File system (folders & files) | Root directory → subfolders → files | Folder or File | Contents inside |
| HTML DOM (web page structure) | <html> → <body> → <div> → <p> | HTML element | Nested elements |
| Family tree / Genealogy | Grandparents → Parents → Children | Person | Children |
| Decision tree (machine learning) | Root question → Yes/No branches → Final decision | Question / Condition | Yes / No branch |
| Tournament bracket | Winner of match → next round | Match / Team | Winner goes up |
| Trie (prefix tree) for autocomplete | Root → first letter → second letter → … | Letter | Possible next letters |
Basic Tree Terminology (must remember these)
| Term | Meaning / Explanation |
|---|---|
| Root | The topmost node (no parent) |
| Parent | Node that has children |
| Child | Node that has a parent |
| Leaf / External node | Node with zero children |
| Internal node | Node with at least one child |
| Edge | Connection between parent and child |
| Depth of node | Number of edges from root to that node |
| Height of node | Number of edges on longest path from that node to a leaf |
| Height of tree | Height of root node |
| Level | All nodes at same depth (root = level 0) |
| Subtree | Tree formed by a node and all its descendants |
Most Important Types of Trees (you must know these)
| Tree Type | Key Property / Constraint | Very Common In Interviews? |
|---|---|---|
| Binary Tree | Each node has at most 2 children | ★★★★★ |
| Binary Search Tree (BST) | Left < Node < Right (for every node) | ★★★★★ |
| Balanced BST (AVL, Red-Black) | Height difference ≤ 1 (or similar balance rule) | ★★★★☆ |
| Complete Binary Tree | All levels filled except possibly last (last level left-filled) | ★★★★☆ (heaps) |
| Full Binary Tree | Every node has 0 or 2 children | ★★★☆☆ |
| Perfect Binary Tree | All internal nodes have 2 children + all leaves at same level | ★★★☆☆ |
| Heap | Complete + parent ≥ children (max) or ≤ (min) | ★★★★★ |
| Trie (Prefix Tree) | Stores strings – each node is a character | ★★★★☆ (autocomplete, dictionary) |
| Segment Tree | Range queries (sum, min, max) in O(log n) | ★★★★☆ (advanced) |
| Binary Indexed Tree (Fenwick) | Range sum queries & updates | ★★★★☆ (competitive coding) |
Binary Tree – Most Important Starting Point
Binary Tree = each node has at most two children (left child & right child)
Visual example:
text
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
1 ← root / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 |
Binary Tree Code Structure (Python – most common interview style)
Python
|
0 1 2 3 4 5 6 7 8 9 10 |
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right |
Most Important Binary Tree Traversals (must master all four)
| Traversal Type | Order of visiting nodes | When used most |
|---|---|---|
| Pre-order | Root → Left → Right | Copy tree, prefix notation |
| In-order | Left → Root → Right | Sorted order in BST |
| Post-order | Left → Right → Root | Delete tree, postfix notation |
| Level-order | Level by level (left to right) | BFS, print tree level-wise |
Code – All four traversals
Python
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
def preorder(root): if not root: return print(root.val, end=" ") preorder(root.left) preorder(root.right) def inorder(root): if not root: return inorder(root.left) print(root.val, end=" ") inorder(root.right) def postorder(root): if not root: return postorder(root.left) postorder(root.right) print(root.val, end=" ") from collections import deque def levelorder(root): if not root: return q = deque([root]) while q: node = q.popleft() print(node.val, end=" ") if node.left: q.append(node.left) if node.right: q.append(node.right) |
Example output for the tree above:
text
|
0 1 2 3 4 5 6 7 8 9 |
Preorder: 1 2 4 8 9 5 3 6 7 Inorder: 8 4 9 2 5 1 6 3 7 Postorder: 8 9 4 5 2 6 7 3 1 Levelorder: 1 2 3 4 5 6 7 8 9 |
Binary Search Tree (BST) – Very Important
Rule (must satisfy for every node):
- All nodes in left subtree < current node
- All nodes in right subtree > current node
- Both left and right subtrees are also BSTs
In-order traversal of BST always gives sorted order.
Common BST operations:
- Insert
- Search
- Delete
- Find min / max
- Find successor / predecessor
- Validate if BST
Quick Summary – Trees at a glance
| Data Structure | Best for | Average Time (search/insert/delete) |
|---|---|---|
| Binary Tree | Hierarchical data, traversals | O(n) |
| Binary Search Tree | Sorted data, fast search (if balanced) | O(h) → O(n) worst, O(log n) balanced |
| Balanced BST (AVL, Red-Black) | Sorted data + guaranteed O(log n) | O(log n) |
| Heap | Get min/max quickly | O(log n) insert/delete, O(1) min/max |
| Trie | String prefix search, autocomplete | O(length of word) |
Most Famous Interview Questions on Trees
Easy → Medium:
- Inorder / Preorder / Postorder / Levelorder traversal
- Height / Depth of tree
- Check if two trees are identical
- Mirror of a binary tree
- Diameter of binary tree
- Lowest Common Ancestor (LCA)
Medium → Hard:
- Validate Binary Search Tree
- Kth smallest element in BST
- Construct BST from preorder / inorder
- Serialize & Deserialize binary tree
- Binary Tree Maximum Path Sum
- Vertical Order Traversal
- Top View / Bottom View / Right View
Want to continue?
Which tree topic would you like to go deep into next?
Very common choices:
- Binary Tree Traversals (recursive + iterative versions)
- Level Order Traversal (BFS style)
- Binary Search Tree – insert, search, delete
- Validate BST
- Lowest Common Ancestor (very frequent)
- Diameter of Binary Tree
- Height vs Depth vs Balanced
Just tell me which one you want — I’ll explain it in the same detailed, step-by-step, human-teacher style with examples and code! 😊
