Open the file manager on any computer and click through folders: College → Semester2 → Assignments → CS. Notice something about how that structure behaves. "Semester2" branches into "Assignments" and "Notes". "Assignments" branches into "CS" and "Maths". You never move sideways from "Notes" to "Maths" directly — you have to climb back up to "Semester2" first and come back down. A folder can have many sub-folders, but every sub-folder has exactly one parent folder. That one rule — every item has exactly one path back to the top — is the entire idea behind a data structure called a tree, and it is completely different from how the data structures you've studied so far behave.
An array or a linked list is linear: element 3 has exactly one neighbour before it and one after it, like people standing in a queue at an IRCTC ticket counter. A tree is non-linear: one node can branch into several children, and those children branch further. Once you notice that folders, organisation charts, the CBSE syllabus tree (Subject → Unit → Chapter → Topic), and a single-elimination cricket knockout bracket all share this same branching shape, you start seeing why trees deserve their own chapter. Then we'll meet an even more general shape — the graph — where the "one parent only" rule is dropped entirely, which is exactly what happens when you model something like the Indian Railways network, where a city can be reached from several other cities at once.
From a line to a branch: why trees needed inventing
Try to store the folder structure above in a plain list: ["College", "Semester2", "Assignments", "Notes", "CS", "Maths"]. The list can tell you the folders exist, but it has completely lost the information about which folder sits inside which. You'd need extra bookkeeping (parent indices, indentation counts) bolted on top of the list to recover the structure — and that bookkeeping is, in effect, reinventing a tree badly. A tree stores the "contains" relationship directly: each node keeps references to its children, so the structure itself carries the meaning, the same way a linked list's "next" pointer carries the meaning of sequence.
This is the general pattern behind every non-linear structure in this chapter: linear structures encode one relationship (comes-before/comes-after). Non-linear structures encode branching or networked relationships, and the shape of the structure has to match the shape of the real relationship you're modelling. Force a tree-shaped relationship into a list, and you lose information. Force a genuinely networked relationship (like train routes, where cities connect to several other cities, not just "up" and "down") into a tree, and you lose information too — which is precisely why graphs exist as a separate, more general structure.
The anatomy of a tree
Before writing any code, fix the vocabulary using a concrete tree. Consider this small binary search tree built from the numbers 50, 30, 70, 20, 40, 60, 80 (we'll construct it step by step in the next section):
Using this picture, here is the exact vocabulary CBSE and every textbook after it will assume you know:
- Node: a single item in the tree — each circle above, holding a value like 50 or 20.
- Root: the one node with no parent — the top of the tree, here the node holding 50. A tree has exactly one root.
- Edge: the connection between a parent and a child — each line in the picture.
- Parent / child: 50 is the parent of 30 and 70; 30 and 70 are children of 50.
- Leaf: a node with no children — 20, 40, 60, 80 above. Leaves are where branching ends.
- Depth of a node: the number of edges from the root down to that node. 50 has depth 0, 30 and 70 have depth 1, the four leaves have depth 2.
- Height of the tree: the depth of its deepest node. This tree has height 2.
- Subtree: any node together with all its descendants, treated as a tree in its own right — e.g. 30 with its children 20 and 40 is a subtree.
One structural rule makes trees easy to reason about: a tree with N nodes always has exactly N−1 edges. Count them above — 7 nodes, 6 edges. Every node except the root is connected to its parent by exactly one edge, and the root has no incoming edge, so the edge count is always one less than the node count. This is also why a tree can never contain a cycle: to create a cycle you would need an extra edge connecting two nodes that already have a path between them through the root, and a tree simply doesn't have that spare edge.
Binary trees, and building one from real numbers
A binary tree is a tree where every node has at most two children, conventionally called left and right. A binary search tree (BST) is a binary tree with one extra rule that makes it useful for fast lookup: for every node, everything in its left subtree is smaller than the node's value, and everything in its right subtree is larger. Let's build the BST shown above by inserting the values 50, 30, 70, 20, 40, 60, 80 one at a time, in that order, and watch the rule enforce itself.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
Trace it by hand, one insertion at a time:
- Insert 50: tree is empty, so 50 becomes the root.
- Insert 30: compare with root 50. Since 30 < 50, go left. Left child is empty, so 30 becomes the left child of 50.
- Insert 70: compare with root 50. Since 70 is not less than 50, go right. Right child is empty, so 70 becomes the right child of 50.
- Insert 20: compare with 50 → 20 < 50, go left to 30. Compare with 30 → 20 < 30, go left. Left of 30 is empty, so 20 becomes the left child of 30.
- Insert 40: compare with 50 → go left to 30. Compare with 30 → 40 is not less than 30, go right. Right of 30 is empty, so 40 becomes the right child of 30.
- Insert 60: compare with 50 → 60 is not less than 50, go right to 70. Compare with 70 → 60 < 70, go left. Left of 70 is empty, so 60 becomes the left child of 70.
- Insert 80: compare with 50 → go right to 70. Compare with 70 → 80 is not less than 70, go right. Right of 70 is empty, so 80 becomes the right child of 70.
That trace produces exactly the tree drawn above. Notice why this shape is useful: to find whether 60 is present, you never scan all 7 numbers. You compare with 50 (go right, because 60 ≥ 50), then with 70 (go left, because 60 < 70), then you land on 60 in just 2 comparisons instead of checking every element the way you would in an unsorted list. This is the entire reason BSTs exist — searching a balanced BST with N nodes takes roughly log₂N comparisons, not N.
Traversals: the three correct ways to read every node exactly once
A list only has one sensible reading order: left to right. A tree has several, because at every node you must decide when to "visit" it relative to its two subtrees. The three standard traversals used in CBSE and everywhere else are defined by where the node itself is visited relative to its left and right subtrees:
def inorder(root, result):
if root is None:
return
inorder(root.left, result)
result.append(root.value)
inorder(root.right, result)
In-order (left, node, right) visits the left subtree fully, then the node, then the right subtree. Trace it on our tree starting at 50: it dives to the leftmost node first. inorder(50) calls inorder(30) before touching 50. inorder(30) calls inorder(20) before touching 30. inorder(20) calls inorder(None) (does nothing), then appends 20, then calls inorder(None) again. Control returns to 30, which appends 30, then calls inorder(40): inorder(None), append 40, inorder(None). Control returns to 50, which appends 50, then calls inorder(70), which by the same logic appends 60, then 70, then 80. The full sequence collected is:
20, 30, 40, 50, 60, 70, 80
That is the sorted order of the original numbers. This is not a coincidence — in-order traversal of any BST always produces the values in ascending sorted order, because the BST rule (left < node < right) is exactly the rule that makes "visit left, then me, then right" equivalent to "visit in increasing order". This is one of the most tested facts about BSTs in board exams and worth memorising by understanding it, not by rote.
The other two traversals only change when the node itself is appended. Pre-order (node, left, right) visits the node before its subtrees, giving 50, 30, 20, 40, 70, 60, 80 — useful for copying a tree's structure, since a parent is always recorded before its children. Post-order (left, right, node) visits the node last, giving 20, 40, 30, 60, 80, 70, 50 — useful for deleting a tree safely, since every child is disposed of before its parent.
Here is a common mix-up worth correcting directly: students often treat "binary tree" and "binary search tree" as the same thing, or assume every tree must have exactly two children per node. Neither is true. A general tree node can have any number of children (think of the folder example: "Assignments" might have three sub-folders, not two). A binary tree specifically restricts nodes to at most two children. A binary search tree is a binary tree with the additional ordering rule described above. All BSTs are binary trees; not all binary trees are BSTs (a binary tree with 70 as the left child of 50 would break the BST rule but is still a perfectly valid binary tree); and neither is the same as a general tree like a folder hierarchy, which usually isn't restricted to two children at all.
Graphs: when "one parent only" stops being true
Trees model hierarchies well, but plenty of real relationships aren't hierarchies. Consider train connectivity between six cities: Delhi, Jaipur, Agra, Kanpur, Lucknow and Udaipur, with direct rail links Delhi–Jaipur, Delhi–Agra, Delhi–Kanpur, Jaipur–Udaipur, Agra–Kanpur and Kanpur–Lucknow. Try to draw this as a tree with Delhi as root: Delhi connects to three cities, fine so far, that's just a node with three children. But Kanpur is reachable from both Delhi directly and from Agra. In a tree, every non-root node has exactly one parent — but Kanpur effectively has two ways to be reached. The moment a node can be reached from more than one other node without going back through a single root, you no longer have a tree. You have the more general structure underneath both trees and networks: a graph.
Notice this picture has no single top node — Delhi just happens to have the most connections, but the structure is a network, not a hierarchy. This is exactly the shape of a WhatsApp contact network, a road map, or the "friends of friends" graph behind a social media suggestion feature — any relationship where connections can loop back and a node can have many independent ways of being reached.
Graph vocabulary and representing a graph in code
A graph consists of vertices (the nodes — cities, here) and edges (the connections — rail links). Our rail graph is undirected because a link Delhi–Agra can be travelled in both directions; a graph modelling one-way streets or "who follows whom" on a social app would be directed, with edges having a specific direction. Our graph is also unweighted — we only recorded whether a link exists, not its distance or fare; a weighted version would attach a number (kilometres, ticket price, travel time) to every edge, which is how real route-planning apps like the ones used for IRCTC journey planning actually work.
To store a graph in a program, the most common representation is an adjacency list: a dictionary mapping each vertex to the list of vertices it connects to directly.
graph = {
"Delhi": ["Jaipur", "Agra", "Kanpur"],
"Jaipur": ["Delhi", "Udaipur"],
"Agra": ["Delhi", "Kanpur"],
"Kanpur": ["Delhi", "Agra", "Lucknow"],
"Lucknow": ["Kanpur"],
"Udaipur": ["Jaipur"]
}
Because the graph is undirected, every edge appears twice — once in each city's list — which is exactly why Delhi appears in Jaipur's list and Jaipur appears in Delhi's list. The alternative representation is an adjacency matrix: a grid with one row and one column per vertex, where a 1 marks a direct connection and a 0 marks its absence. For the same six cities (ordered Agra, Delhi, Jaipur, Kanpur, Lucknow, Udaipur):
A D J K L U
Agra 0 1 0 1 0 0
Delhi 1 0 1 1 0 0
Jaipur 0 1 0 0 0 1
Kanpur 1 1 0 0 1 0
Lucknow 0 0 0 1 0 0
Udaipur 0 0 1 0 0 0
Both representations store identical information; the adjacency list is more memory-efficient when most cities are not directly connected to each other (true for real rail networks, where each station connects to only a handful of others, not all of them), while the matrix makes "is city X directly connected to city Y?" a single lookup instead of a search through a list. CBSE problems generally expect you to read and build adjacency lists comfortably; recognise the matrix as the alternative you'll meet later.
Visiting every city exactly once: Breadth-First Search
With a tree, "visit every node" was simple because there's no way to revisit a node by accident — a tree has no cycles. A graph can have cycles (imagine an extra direct link Udaipur–Kanpur added to our map — you could then go Delhi → Jaipur → Udaipur → Kanpur → Delhi and loop forever). So every graph traversal algorithm must explicitly remember which vertices it has already visited. Breadth-first search (BFS) visits the start vertex, then all vertices exactly one link away, then all vertices exactly two links away, and so on — the same way information spreads outward in rings. It uses a queue, exactly like the queue data structure from earlier chapters:
def bfs(graph, start):
visited = {start}
queue = [start]
order = []
while queue:
node = queue.pop(0)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
Trace bfs(graph, "Delhi") step by step. Start: visited = {Delhi}, queue = [Delhi]. Dequeue Delhi, record it in order. Its neighbours are Jaipur, Agra, Kanpur — none visited yet, so all three are marked visited and pushed onto the queue: queue = [Jaipur, Agra, Kanpur]. Dequeue Jaipur, record it. Its neighbours are Delhi (already visited, skip) and Udaipur (new) — push Udaipur: queue = [Agra, Kanpur, Udaipur]. Dequeue Agra, record it. Neighbours Delhi (visited) and Kanpur (already visited, skip): queue unchanged apart from the dequeue, queue = [Kanpur, Udaipur]. Dequeue Kanpur, record it. Neighbours Delhi (visited), Agra (visited), Lucknow (new) — push Lucknow: queue = [Udaipur, Lucknow]. Dequeue Udaipur, record it; its only neighbour Jaipur is visited. Dequeue Lucknow, record it; its only neighbour Kanpur is visited. Queue empty, stop.
The final order recorded is Delhi, Jaipur, Agra, Kanpur, Udaipur, Lucknow — Delhi first, then everything one hop away (Jaipur, Agra, Kanpur, in the order they were discovered), then everything two hops away (Udaipur, Lucknow). This ring-by-ring pattern is exactly why BFS is the standard method for finding the shortest path in an unweighted graph: the first time BFS reaches a vertex, it has necessarily done so using the fewest possible links, since it always exhausts every one-hop vertex before trying any two-hop vertex.
Going deep before going wide: Depth-First Search
Depth-first search (DFS) takes the opposite strategy: from the current vertex, plunge into one unvisited neighbour, then from there plunge into one of its unvisited neighbours, and keep going until you hit a dead end, only then backing up to try a different branch. It is naturally written as recursion, using the same visited set to avoid the infinite loop a cycle would otherwise cause:
def dfs(graph, node, visited=None, order=None):
if visited is None:
visited = set()
order = []
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited, order)
return order
Trace dfs(graph, "Delhi"): visit Delhi, record it. First unvisited neighbour is Jaipur — recurse into it immediately (this is the "depth" part: we don't finish looking at Delhi's other neighbours first). Visit Jaipur, record it. Jaipur's neighbours are Delhi (visited, skip) and Udaipur (unvisited) — recurse into Udaipur. Visit Udaipur, record it. Udaipur's only neighbour, Jaipur, is visited, so this branch ends and control returns to Jaipur, which has no more neighbours, so it returns to Delhi. Back in Delhi's loop, the next neighbour is Agra (unvisited) — recurse. Visit Agra, record it. Agra's neighbours are Delhi (visited) and Kanpur (unvisited) — recurse into Kanpur. Visit Kanpur, record it. Kanpur's neighbours are Delhi (visited), Agra (visited), and Lucknow (unvisited) — recurse into Lucknow. Visit Lucknow, record it; its only neighbour Kanpur is visited, so everything now unwinds back to Delhi, whose last neighbour, Kanpur, is already visited, so the call ends.
The final order is Delhi, Jaipur, Udaipur, Agra, Kanpur, Lucknow — notice it commits fully to the Jaipur–Udaipur branch before even looking at Agra, unlike BFS, which explored all of Delhi's direct neighbours first. Same graph, same starting point, genuinely different visiting order — this is the detail students most often get wrong when asked to trace BFS versus DFS by hand, so always check whether the question demands "ring by ring" (BFS, queue) or "commit to a path, backtrack on dead ends" (DFS, recursion or stack).
Here is the second misconception worth naming directly: because tree traversals (in-order, pre-order, post-order) never needed a visited set, some students carry that habit into graphs and write a traversal that doesn't track visited vertices. On a tree this is harmless, since a tree has no cycles, so recursion always terminates on its own. On a graph, skipping the visited set is a real bug: if our map had one more direct link, say Udaipur–Kanpur, an unguarded traversal could cycle Delhi → Jaipur → Udaipur → Kanpur → Delhi → Jaipur → … forever. The visited set isn't a stylistic extra in graph algorithms; it is the one thing that makes BFS and DFS on a graph guaranteed to terminate.
Trees are graphs, not a separate topic
It's worth stating explicitly what the last two sections quietly implied: a tree is not an unrelated structure that happens to be taught next to graphs — a tree is a graph, specifically a connected graph with no cycles and one designated root. Every fact you already know about trees is a special case of a more general graph fact: a tree traversal is a graph traversal on a graph that happens to need no visited set (because it cannot have cycles); "N nodes, N−1 edges" is true only because a tree is the minimal connected graph on N vertices — add even one more edge to a tree and you necessarily create exactly one cycle. Recognising this relationship saves you from memorising tree algorithms and graph algorithms as two separate syllabuses; almost everything you need for graphs is "the tree idea, plus a visited set, because cycles are now allowed."
Check your understanding
- Insert the values 15, 6, 18, 3, 9, 20 into an empty BST in that order. Draw the resulting tree, then write the in-order traversal without doing any additional sorting.
- A tree has 12 nodes. How many edges must it have, and why can you answer this without seeing the tree's shape?
- For the rail-network graph in this chapter, run BFS starting from Lucknow instead of Delhi. Write out the visiting order.
- Explain, using the Udaipur–Kanpur example from this chapter, why a graph traversal needs a visited set even though a tree traversal does not.
- Is a WhatsApp group's "who has messaged whom" relationship better modelled as a tree or a graph? Justify your answer using the definitions from this chapter.
Answers with reasoning: (1) Following the same left-if-smaller rule used for 50/30/70/… above, the tree has root 15, left child 6, right child 18; 6's left child is 3 and right child is 9; 18's right child is 20. In-order traversal (left, node, right) gives 3, 6, 9, 15, 18, 20 — sorted, exactly as the BST guarantee predicts. (2) 11 edges. Every tree with N nodes has N−1 edges regardless of shape, because every node except the root contributes exactly one edge connecting it to its parent. (3) Starting the same BFS logic from Lucknow: queue starts at Lucknow, its only neighbour is Kanpur (visit), Kanpur's unvisited neighbours are Delhi and Agra (visit both, Delhi discovered before Agra since it appears first in Kanpur's list), then Delhi's unvisited neighbour Jaipur (visit), then Agra's neighbours are already visited, then Jaipur's unvisited neighbour Udaipur (visit). Order: Lucknow, Kanpur, Delhi, Agra, Jaipur, Udaipur. (4) A tree traversal is safe without a visited set only because a tree structurally cannot contain a cycle (N−1 edges rule); the moment an extra edge like Udaipur–Kanpur exists, a cycle becomes possible, and an unguarded traversal would revisit the same vertices forever, so the algorithm must remember what it has already seen. (5) A graph — messaging relationships have no single root and no "one parent per person" restriction; any member can message any other member directly, which is exactly the networked, cycle-permitting structure a graph (not a tree) is built to represent.
Summary
Linear structures (arrays, linked lists, stacks, queues) encode a single before/after relationship. Trees are the first non-linear structure: hierarchical data where each node has exactly one parent and any number of children, built from vocabulary like root, edge, parent, child, leaf, depth and height, with the guaranteed property that N nodes always need exactly N−1 edges. Binary trees cap children at two per node; binary search trees add an ordering rule (left < node < right) that makes searching take roughly log₂N steps instead of N and makes in-order traversal automatically produce sorted output. Graphs generalise trees further by dropping the one-parent rule and allowing cycles, and are represented in code as adjacency lists or adjacency matrices; because cycles are now possible, every graph traversal — BFS (queue-based, ring by ring, used for shortest paths in unweighted graphs) and DFS (stack/recursion-based, plunge and backtrack) — must maintain a visited set that tree traversals never needed. Understanding trees and graphs as one family, with the tree as the acyclic special case, is what turns two intimidating new topics into a single coherent idea.
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 trees and graphs: non-linear data structures 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 trees and graphs: non-linear data structures to at least 3 other topics you have studied.