A Register That Isn't a List
Open the DigiLocker app (India's government-run digital document wallet) and you don't see one long scroll of every certificate you own. You see a folder called "Issued Documents" that branches into categories such as "Education," "Vehicle," and "Health ID." Open "Education" and it branches again into "Class X Marksheet" and "Class XII Marksheet." Open "Vehicle" and you find "Driving Licence" and "RC Book." UMANG works the same way, and so does the file manager on any phone: one starting point, branching into groups, branching further into individual items that don't branch any more.
This branching shape has a name — a tree — and it is a completely different way of organising data from the list or array you have used so far. In a list, item 5 has exactly one neighbour before it and one after it; to reach item 5 you typically walk past 1, 2, 3, and 4. In a tree, "Driving Licence" has no relationship at all to "Class X Marksheet" except that they share a distant common ancestor (DigiLocker itself). You reach any document by following a short path of branches, not by scanning everything that came before it. That difference — branching instead of a straight line — is what makes trees worth a chapter of their own, and it is the idea this chapter builds from the ground up.
Tree Vocabulary, Made Precise
The picture above gives us every word we need, attached to something concrete:
- Node — one box (DigiLocker, Education, Class X Marksheet, ...). Each node can store data (here, a folder or document name).
- Root — the single node with no parent: DigiLocker. Every tree has exactly one root.
- Edge — the line connecting a node to the node directly below it. It represents "contains" or "leads to."
- Parent / Child — DigiLocker is the parent of Education, Vehicle and Health ID; those three are its children. Education is, in turn, the parent of Class X Marksheet and Class XII Marksheet.
- Sibling — nodes sharing the same parent, such as Class X Marksheet and Class XII Marksheet.
- Leaf — a node with zero children. All four documents are leaves; the tree stops there.
- Subtree — any node together with everything below it. "Education and its two documents" is a subtree of the whole DigiLocker tree.
- Depth of a node — the number of edges on the path from the root down to that node. Depth of DigiLocker is 0; depth of Education is 1; depth of Class X Marksheet is 2.
- Height of a tree — the depth of its deepest leaf (equivalently, the number of edges on the longest root-to-leaf path). This DigiLocker tree has height 2.
Notice that DigiLocker's tree is not a binary tree — the root has three children, more than the two a binary tree allows. General trees like this are common (a syllabus outline, a company's reporting structure, a file system), but from here on this chapter narrows to the specific, extremely important case where every node has at most two children.
Meet a Binary Tree: A Class Register by Roll Number
Suppose your CBSE class teacher keeps a small digital register of 7 students, indexed by roll number, and wants to store it as a tree instead of a flat list, so any student's marks can be found quickly. She inserts the roll numbers in this order: 45, 23, 67, 12, 34, 56, 78. Each new roll number is placed by a simple rule: compare it to the current node; if it is smaller, go left; if it is larger, go right; when you fall off the tree (reach an empty spot), place the new node there.
Tracing all seven insertions by hand: 45 becomes the root (the tree was empty). 23 is smaller than 45, so it becomes the root's left child. 67 is larger than 45, so it becomes the root's right child. 34 is compared to 45 (smaller, go left) then to 23 (larger, go right) then placed as 23's right child. 12 is compared to 45 (smaller), then 23 (smaller), then placed as 23's left child. 56 is compared to 45 (larger), then 67 (smaller), placed as 67's left child. 78 is compared to 45 (larger), then 67 (larger), placed as 67's right child. The result is the tree below — every node here has at most two children, so this is a binary tree, and each child is labelled specifically left or right (unlike the DigiLocker tree, where "first child" and "second child" had no left/right meaning).
Each node here can be written in code as an object with a value and two pointers, exactly matching the two branches drawn above:
class Node:
def __init__(self, roll, marks):
self.roll = roll # key used to order the tree
self.marks = marks # any extra data riding along with the key
self.left = None
self.right = None
Walking the Tree: The Four Traversals
A list has one obvious order: front to back. A tree has no single obvious order — at every node you must decide when to visit the node itself versus its left and right subtrees. Four traversal orders cover almost everything you will ever need, and all four can be run on any binary tree, BST or not.
Inorder (left subtree, then the node, then right subtree) on our tree visits 12, 23, 34, 45, 56, 67, 78 — sorted order, which is not a coincidence and is explained in the next section.
Preorder (the node, then left subtree, then right subtree) visits 45, 23, 12, 34, 67, 56, 78 — the root always comes first, which is useful when you need to rebuild the tree's shape from scratch (for example, serialising a tree to a file).
Postorder (left subtree, then right subtree, then the node) visits 12, 34, 23, 56, 78, 67, 45 — the root always comes last, which is useful when you must process children before their parent (for example, deleting every node safely, or computing the size of each subtree bottom-up).
Level-order (also called breadth-first traversal: visit depth 0, then all of depth 1, then all of depth 2, ...) visits 45, 23, 67, 12, 34, 56, 78 — useful whenever "closer nodes first" matters, such as searching layer by layer.
The three depth-first orders share one recursive shape and differ only in where the "visit the node" line sits:
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.roll) # visit AFTER left, BEFORE right
inorder(node.right, out)
return out
def preorder(node, out):
if node:
out.append(node.roll) # visit BEFORE both subtrees
preorder(node.left, out)
preorder(node.right, out)
return out
def postorder(node, out):
if node:
postorder(node.left, out)
postorder(node.right, out)
out.append(node.roll) # visit AFTER both subtrees
return out
Level-order needs a queue instead of recursion, because it processes the tree layer by layer rather than branch by branch:
from collections import deque
def level_order(root):
out, q = [], deque([root])
while q:
node = q.popleft()
if node:
out.append(node.roll)
q.append(node.left)
q.append(node.right)
return out
The Binary Search Tree Rule
Every binary tree supports the four traversals above. What made this particular tree's inorder walk come out sorted was not luck — it was the placement rule the class teacher used while inserting (smaller goes left, larger goes right). A binary tree built that way is called a binary search tree (BST), and it obeys one invariant everywhere, not just between neighbours:
BST property: for every node N, every key in N's left subtree is smaller than N's key, and every key in N's right subtree is larger than N's key.
Check it on our tree: node 45's entire left subtree is {23, 12, 34} — all smaller than 45 — and its entire right subtree is {67, 56, 78} — all larger. The same holds at node 23 (left subtree {12} < 23 < right subtree {34}) and at node 67 (left {56} < 67 < right {78}). Because this "smaller-left, larger-right" pattern is true at every node, walking left-root-right always visits keys in increasing order — that is exactly why inorder traversal of a BST always produces a sorted list, for any BST whatsoever, not just this one.
A plain binary tree only needs each node to have at most two children; it says nothing about what values go where. A BST is a binary tree with that extra ordering promise layered on top. Every BST is a binary tree; most binary trees are not BSTs.
Searching a BST: Why It Beats a Flat List
Say the teacher wants roll number 56's marks. Searching a flat, unordered list of 7 roll numbers can force you to check all 7 in the worst case (linear search, O(n)). Searching the BST instead exploits the ordering promise at every step:
def search(node, roll):
if node is None or node.roll == roll:
return node
if roll < node.roll:
return search(node.left, roll)
return search(node.right, roll)
Tracing search(root, 56): at 45, since 56 > 45, go right. At 67, since 56 < 67, go left. At 56, the key matches — found. That is 3 comparisons to search 7 records, because each comparison eliminates an entire subtree rather than a single element. In general, a search visits at most height + 1 nodes — one per level from the root down to where the key is found (or to an empty spot, confirming it is absent). For a balanced tree of n nodes, height is about log₂n, so search costs O(log n): doubling the register from 1,000 students to 2,000 adds only one extra comparison in the worst case, not a thousand more.
Inserting into a BST
Insertion reuses the exact same left/right decision as search, just replacing "empty spot" with "place the new node here":
def insert(node, roll, marks):
if node is None:
return Node(roll, marks)
if roll < node.roll:
node.left = insert(node.left, roll, marks)
elif roll > node.roll:
node.right = insert(node.right, roll, marks)
return node # duplicate roll numbers are ignored here
Trace insert(root, 40, marks): 40 < 45, go left to 23. 40 > 23, go right to 34. 40 > 34, and 34 has no right child, so 40 becomes 34's new right child. Three comparisons, same cost pattern as search, because insertion is a search that stops at the first empty spot instead of at a match.
Deleting from a BST
Deletion is the trickiest of the three because removing a node must not break the BST property for the nodes left behind. There are three cases:
- Deleting a leaf (no children): simply remove it. Nothing else needs to change.
- Deleting a node with one child: the node's single child takes its place — the parent now points directly to the grandchild.
- Deleting a node with two children: you cannot just remove it (which child would take its place?). Instead, find its inorder successor — the smallest key in its right subtree, found by walking left as far as possible from the right child — copy that key up into the node being deleted, and then delete the successor from the right subtree (where it is guaranteed to have at most one child, reducing to an easier case).
def find_min(node):
while node.left:
node = node.left
return node
def delete(node, roll):
if node is None:
return node
if roll < node.roll:
node.left = delete(node.left, roll)
elif roll > node.roll:
node.right = delete(node.right, roll)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
successor = find_min(node.right)
node.roll, node.marks = successor.roll, successor.marks
node.right = delete(node.right, successor.roll)
return node
Trace delete(root, 23) on the original seven-node tree: node 23 has two children (12 and 34), so this is the hard case. Its inorder successor is the smallest key in its right subtree — walk left from 34, but 34 has no left child, so 34 itself is the successor. Copy 34's value into node 23's slot, then delete the original 34 (a leaf, the easy case) from the right subtree. The tree that remains has root 45, whose left child now holds the value 34 with a left child of 12 and no right child, and whose right child 67 is unchanged with children 56 and 78. Six nodes, BST property still intact: 45's left subtree {34, 12} is still entirely smaller than 45.
Misconception #1: "A BST Is Always Fast"
Many students assume that just being a binary search tree guarantees O(log n) search. It does not — the guarantee depends entirely on the tree's shape, which depends on insertion order. Suppose, instead of 45, 23, 67, 12, 34, 56, 78, the same seven roll numbers had been inserted already sorted: 12, 23, 34, 45, 56, 67, 78. Insert 12 (becomes root). Insert 23: larger than 12, no left subtree to compare against, becomes 12's right child. Insert 34: larger than 12, larger than 23, becomes 23's right child. Every subsequent number is larger than everything before it, so every new node becomes the right child of the previous one. The result is a "tree" that is really a chain — each node has only a right child, height 6, and searching for 78 now takes 7 comparisons, the same as scanning a plain list. This is called a degenerate or skewed BST, and it is the single most important thing to know about BSTs: correctness (the ordering property) and speed (a short height) are separate guarantees. A plain BST only promises the first one.
This is also where a subtle earlier point needs sharpening. It is true that any binary tree of height h holds at most 2h+1−1 nodes, achieved only when the tree is perfect (every level completely full, as in our first roll-number tree: height 2, 7 = 2³−1 nodes). But that bound is a ceiling that applies to any binary tree of that height, balanced or not — it says nothing about how short the tree can be made to hold a given number of nodes. What balance actually controls is the other direction: a balanced tree keeps height as close as possible to log₂n for its node count (self-balancing structures such as AVL trees and red-black trees enforce this automatically after every insertion and deletion), which is what keeps search, insert and delete at O(log n). A plain, unbalanced BST offers no such enforcement, so its height — and therefore its speed — depends entirely on the order data arrives in.
Misconception #2: Checking Only the Immediate Children Is Not Enough
A second common bug appears when students write code to verify whether a given binary tree is a valid BST. The tempting shortcut is to check only the direct parent-child relationship: "is the left child smaller than its parent, and the right child larger?" This local check is insufficient, because the BST property applies to entire subtrees, not just immediate neighbours. Consider a tree with root 50, left child 30, and 30's right child 60. Locally, 30 < 50 (fine) and 60 > 30 (fine) — every parent-child pair looks correct. But 60 sits in 50's left subtree while being larger than 50, which violates the real property (everything in the left subtree must be smaller than the root). A correct validator must carry a shrinking valid range down the recursion — every node in a subtree must fall strictly between the nearest ancestor bounds established so far, not merely satisfy its immediate parent.
Complexity Summary
| Operation | Balanced BST (height ≈ log₂n) | Skewed/degenerate BST (height ≈ n) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Inorder traversal (visits every node once) | O(n) | O(n) |
Test Yourself
- Q: A BST is built by inserting, in order: 50, 20, 70, 10, 30, 60, 80. Write its preorder traversal.
A: 50, 20, 10, 30, 70, 60, 80 (root first, then the whole left subtree, then the whole right subtree — this tree has exactly the same shape as our roll-number example, just with different numbers). - Q: What is the height of the tree in question 1, and how many nodes does a tree of that height hold at most?
A: Height 2 (root at depth 0, 20/70 at depth 1, 10/30/60/80 at depth 2). Maximum nodes at height 2 is 23−1 = 7, which this tree achieves exactly because it is perfect. - Q: Roll numbers 5, 10, 15, 20, 25 are inserted into an empty BST in that exact order. What does the tree look like, and what is its height?
A: Every node becomes the right child of the previous one (a completely skewed, degenerate tree), so its height is 4 — one less than the number of nodes, the worst case for a BST of 5 nodes. - Q: Is "check each node against only its direct parent" a correct way to verify a tree is a valid BST? Why or why not?
A: No. The BST property constrains entire subtrees, not just parent-child pairs; a node can satisfy its immediate parent while still violating the range set by a grandparent or earlier ancestor, as in the 50/30/60 example above. A correct check must track a valid (min, max) range that narrows as the recursion descends. - Q: You delete a node that has exactly one child from a BST. What replaces it?
A: The node's single child is linked directly to the deleted node's former parent, taking the deleted node's place in the tree. - Q: Why does inorder traversal of any BST always produce sorted output, while preorder and postorder do not?
A: Inorder visits a node's entire left subtree (all smaller keys) before the node, and the node before its entire right subtree (all larger keys); applied recursively at every node, this guarantees increasing order throughout. Preorder and postorder visit the root relative to its children at a fixed position (first or last) regardless of key size, so they reflect the tree's insertion shape, not numeric order.
Summary
A tree is data organised by branching rather than by sequence: one root, parent-child edges, and leaves where the branching stops, as seen in a DigiLocker-style folder hierarchy. A binary tree narrows that idea to at most two children per node, distinguished as left and right, which is what makes the four traversals (inorder, preorder, postorder, level-order) well-defined and enables the height-based capacity bound 2h+1−1. A binary search tree adds one further promise on top of the binary-tree shape — every node's left subtree holds only smaller keys and its right subtree only larger keys — and that single promise is what turns search, insert and delete into O(height) operations instead of O(n) scans, and what makes inorder traversal double as a sorting method. But the promise is about ordering, not about shape: nothing stops a BST from degenerating into a height-n chain if data arrives in sorted order, which is exactly why real systems reach for self-balancing variants (AVL trees, red-black trees) when worst-case speed must be guaranteed rather than merely typical.
Think About It
Think about this: How would you explain binary trees and bst: hierarchical data mastery to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.
Practice Exercises
Now it is time to practice! Complete these challenges to solidify your understanding:
- Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
- Exercise 2: Find a real-world example where binary trees and bst: hierarchical data mastery is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
- Exercise 3: Create a mind-map connecting binary trees and bst: hierarchical data mastery to at least 3 other topics you have studied.