Trees & Binary Trees Explained: Terminology, Traversals & Recursion

Open the file manager on your phone: Internal storage → DCIM → Camera → a photo. Or your college's org chart: principal → HODs → professors → students. Or this very page's address: cs → dsa → data-structures.

Try to store any of these in a list. Where does "Camera" go — before or after "Downloads"? The question itself is wrong: these things aren't in a line at all. They are things containing things — hierarchy. Every structure so far (array, list, stack, queue) was a line. Today we get the structure for hierarchy: the tree.

Six words you must own

• Root — the single starting node at the top. (CS trees grow upside-down, like a family tree.)
• Parent / child — the node above / the nodes directly below it.
• Leaf — a node with no children; where a branch ends.
• Depth of a node — edges from the root down to it. The root has depth 0.
• Height of a node — edges from it down to its deepest leaf. Leaves have height 0; the tree's height is the root's height.

Careful with the last two — most students have them swapped. The memory hook: depth is measured from the root; height is measured to the leaves — exactly like a well's depth (from the top) and a building's height (from the ground). Interviewers ask this precisely because half the room gets it backwards.

Binary trees, in code

A binary tree caps every node at two children — called left and right. "Why two? My file manager has twenty folders in one folder." True — general trees allow any number. We study the binary kind because two-way branching is the minimal shape that supports halving — the log n engine you'll switch on in lesson 7. Learn binary deeply and general trees are a loop over children.

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None       # left child
        self.right = None      # right child

#        1
#      /   \
#     2     3
#    / \
#   4   5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

Look familiar? It's a linked list node with two next-pointers instead of one. All the pointer discipline from lesson 3 — save before you overwrite, mind the None ends — carries over directly. You have seen a simpler version of this structure before.

The one observation that unlocks every tree problem

Look at the tree above and focus on node 2, ignoring everything else. Node 2 with its children 4 and 5 is... itself a complete little tree. Every child of a tree node is the root of a smaller tree.

That observation is the master key, because it means any question about a tree can be answered by combining answers about its two subtrees. To define a tree function you need exactly two lines of truth:

1. What's the answer for the empty tree (None)? 2. Given the answers for my left and right subtrees, what's my answer?

And here is the discipline that separates people who find trees easy from people who find them terrifying: do NOT trace into the recursive calls. Trust them. Assume the subtree answers are correct and combine them — the same leap of faith you use for a loop ("it will reach the end") without re-proving it each time.

Let's write our first tree functions

Count the nodes. Empty tree: 0. A node: myself (1) + whatever my left subtree counts + whatever my right subtree counts. Translate directly:

def count_nodes(node):
    if node is None:          # answer for the empty tree
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

Maximum depth (in nodes). Empty tree: 0. A node: 1 (for me) + the depth of my taller subtree:

def max_depth(node):
    if node is None:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))

print(count_nodes(root), max_depth(root))

5 3

Verify against the picture: 5 nodes ✓, and the longest chain 1 → 2 → 4 has 3 nodes ✓. Two lines of truth each, no tracing. Every tree function in this course — and most tree interview questions — has exactly this skeleton.

Reading a tree: the four traversals

A list has one natural reading order. A tree has none — at every node, do you visit yourself first, or your left subtree, or your right? So we define the orders. Three are recursive, differing only in when the node itself is visited:

def preorder(node):              # NODE, left, right
    if node:
        print(node.val, end=" ")
        preorder(node.left)
        preorder(node.right)

def inorder(node):               # left, NODE, right
    if node:
        inorder(node.left)
        print(node.val, end=" ")
        inorder(node.right)

def postorder(node):             # left, right, NODE
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.val, end=" ")

Same three lines each time — only the print moves. And each order has a job: preorder (parent before children) is for copying and serialising a tree top-down; postorder (children before parent) is for deleting and size-computing — never act on a node whose subtrees are pending; inorder is the star of the next lesson, where it produces sorted output on a special tree.

Dry run: inorder, step by step

Let's dry run inorder on our tree — root 1, children 2 and 3, node 2 having children 4 and 5. Remember the rule at every node: finish the ENTIRE left subtree, then me, then the right subtree.

inorder(1): first, entire left subtree of 1 (rooted at 2)
  inorder(2): first, entire left subtree of 2 (rooted at 4)
    inorder(4): left is None -> print 4 -> right is None
  back at 2: left done -> print 2
    inorder(5): left None -> print 5 -> right None
back at 1: left done -> print 1
  inorder(3): left None -> print 3 -> right None

output: 4 2 5 1 3

Cross-check with the diagram above: preorder gives 1 2 4 5 3 (node first), postorder gives 4 5 2 3 1 (node last). One tree, three readings — and "write the three traversals of this tree" is a guaranteed written-round question that this dry-run habit makes free marks.

Level order: the queue returns

The fourth order reads by floors: root, then everything at depth 1, then depth 2 — like reading an org chart rank by rank. Which structure serves things in first-discovered, first-served order? You met it two lessons ago.

from collections import deque

def level_order(root):
    if not root:
        return []
    out = []
    q = deque([root])              # the queue of discovered nodes
    while q:
        node = q.popleft()         # serve the oldest discovery
        out.append(node.val)
        if node.left:
            q.append(node.left)    # discover children -> back of the line
        if node.right:
            q.append(node.right)
    return out

print(level_order(root))

[1, 2, 3, 4, 5]

Why does a queue give floors? Parents are discovered before children, so parents are served before children — FIFO preserves the discovery generations. This is BFS on a tree, and the recursive traversals are DFS riding the call stack. Stack → deep, queue → wide — lesson 4's pairing, now doing real work. It returns at full scale in the graphs lessons.

The doubling fact (why height 20 is enough)

One arithmetic fact powers the next three lessons, so let's earn it. Each level of a full binary tree holds double the previous: 1, 2, 4, 8... So a full tree of height h holds 2^(h+1) − 1 nodes:

height 10  ->      2,047 nodes
height 20  ->   ~20 lakh nodes
height 30  ->  ~200 crore nodes

Now read it backwards, because that's the direction that pays: 10 lakh values need a tree only ~20 levels tall. If every operation walks one root-to-leaf path, every operation costs ~20 steps — the log n from lesson 1, wearing branches.

The catch — and it's the entire drama of lesson 7: that arithmetic assumes the tree is bushy. Nothing stops a binary tree from growing as one long chain, height n, where the magic dies. Keeping trees short and bushy is a real engineering problem, coming next.

What if...?

What if the tree is empty? Every function above starts with the None check, so: count 0, depth 0, traversals print nothing, level order returns []. The None base case IS the empty-tree answer — write it first, always.

What if a node has only one child? Perfectly legal. The recursion handles it silently (the missing side contributes its None answer) — but code that writes node.left.val without checking crashes here. Test the one-child shape in your head before submitting.

What if the tree is a chain — every node one child? Everything still works, but O(h) becomes O(n): recursion goes n frames deep (Python's ~1000 limit says hello), and all the height-based promises collapse. This is the degenerate case lesson 7 is built around.

What if I need the traversal without recursion? Replace the call stack with an explicit stack of nodes. Preorder is easy (push right, then left); iterative inorder is a favourite interview upgrade because it tests whether you know what the call stack was doing for you.

Common mistakes

• Swapping height and depth — depth from the root, height to the leaves.
• Mismatched base case: returning 0 for None while counting height in edges makes a leaf height 1. State your convention (nodes or edges), then match the base case to it.
• Tracing into recursive calls instead of trusting them — the fastest way to get lost in any tree problem.
• Using recursion (a stack) for level order — that gives depth-first; floors need a queue.
• Assuming two children everywhere — one-child nodes are legal and crash careless code.
• Mixing up complete (filled left-to-right — heaps), full (0 or 2 children) and balanced (height ≈ log n) — three different words.

How do I recognise tree problems?

• The data contains itself (folders in folders, comments with replies, org charts, JSON) → it's a tree; model it as one.
• "level by level", "zigzag", "left/right view", "width" → level order with a queue.
• "height / depth / count / sum / mirror / same-tree" → the two-lines-of-truth recursion.
• "delete the tree", "compute from children up" → postorder; "copy/serialise top-down" → preorder.

And when you meet ANY new tree question, start by writing the two base-case-and-combine lines in plain English before any code. The code is those two lines, translated.

Quick revision

One thing to remember

Every tree node is the root of a smaller tree — so answer None, combine the subtree answers, and trust the recursion. That one habit turns every tree question into two lines of truth.

Practice Zone — PYQs from real selection rounds

Six MCQs, then three foundations: counting nodes and leaves, a level-order trace, and max depth explained the interview way.

Q1Treeseasy

In a tree, a LEAF is:

Asked in

aThe topmost nodebA node with no childrencA node with exactly one childdAny node that stores data

Q2Treeseasy

Height of a node vs depth of a node — which is correct?

Asked in

aHeight counts down from the root; depth counts up from the leavesbDepth = edges from the ROOT down to the node; height = edges from the node down to its deepest LEAFcThey are always equaldHeight is measured in nodes, depth in edges

Q3Traversalsmedium

For this tree — root 1, left child 2, right child 3, and 2 has children 4 and 5 — the INORDER traversal is:

Asked in

a1, 2, 4, 5, 3b4, 2, 5, 1, 3c4, 5, 2, 3, 1d1, 2, 3, 4, 5

Q4Traversalsmedium

Level-order traversal (top to bottom, left to right) is implemented with:

Asked in

aRecursion, like the other traversalsbA queue — dequeue a node, visit it, enqueue its childrencA stack — push children, pop deepest firstdSorting the nodes by value

Q5Treesmedium

A binary tree has height h (edges). The MAXIMUM number of nodes it can hold is:

Asked in

a2hbh²c2^(h+1) − 1dh!

Q6Recursion on treeshard

This function computes the height of a tree. What is the correct base case? def height(node): return ??? if node is None else 1 + max(height(node.left), height(node.right))

Asked in

a0b-1c1dNone

Hands-on tasks:

FAQ

Hierarchy unlocked. Next, we add ONE ordering rule to this structure — and search becomes the dictionary trick — Lesson 7: Binary Search Trees →