Tree Foundations

11 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

What Is a Tree?

A tree is a way to represent hierarchical relationships. Think of a family tree, a company org chart, or folders inside folders on your computer. There is one starting point (the root), and from there, things branch out. No cycles: you never come back to the same point. In programming, we use trees to represent data that grows in branches.

# In code, a whole tree is just ONE variable:
tree = root            # the top node

# every other node is reached by
# following pointers down from the root

Start from something you already know: folders

Open your computer's file explorer. There's a top folder; inside it, more folders; inside those, still more. Nothing in your Documents folder loops back around to contain Documents itself: the structure only ever branches DOWNWARD. Congratulations: you have been using trees your whole life. A tree is nothing more than this shape, drawn as circles and lines.

Every tree starts at a single topmost node called the ROOT (computer science trees grow upside-down, root at the top). Each connection runs from a node to the nodes directly below it, and those lower nodes can branch again, level after level, until branches end.

The one rule that makes a tree a TREE

Lots of structures have circles and lines, what makes THIS one special? One law: between the root and any node there is EXACTLY ONE path. Not zero (everything is reachable), not two (no shortcuts, no cycles). From the root you can reach every node, and there's never a second way to get there.

Test the law mentally: could a node have TWO parents? No, then two paths would lead to it from above. Could a branch loop back up to an ancestor? No: that would create a cycle, and walking 'down' could bring you back where you started. This one-path law is why tree algorithms are so clean: walk downward and you will visit everything exactly once, guaranteed, with no bookkeeping.

Meet the family: how we talk about trees

Tree vocabulary is family vocabulary, and it sticks because the picture matches. A node directly above another is its PARENT; the nodes directly below are its CHILDREN; children of the same parent are SIBLINGS. Nodes with no children at all, the ends of the branches, are called LEAVES, just like a real tree.

In the tree below: 1 is the root and the parent of 2 and 3. Nodes 2 and 3 are siblings. Node 2 is simultaneously a CHILD (of 1) and a PARENT (of 4 and 5), most nodes wear both hats. Nodes 4, 5, and 3 have no children, so they're the leaves.

The same tree, written as code

Here's the leap that surprises beginners: in code there is no drawing. A tree is just node objects pointing at each other, and your program holds a single variable, the root. Everything else is reached by following pointers downward, exactly like clicking through folders.

Read the code and match it to the family photo above: we create five nodes, then wire 1's left hand to 2, 1's right hand to 3, and so on. Hand a function the root and it can reach all five nodes. Lose the root and the whole tree is gone. Which is why every tree function you'll ever write takes `root` as its first argument.

Why programmers reach for trees

Trees show up wherever data is naturally hierarchical or needs to be searched fast. Your file system is a tree. Every HTML page is a tree of tags (that's literally what 'the DOM tree' means). Company org charts, comment threads with replies, tournament brackets, the folder of chess moves a game engine considers, all trees. And in later lessons you'll meet the Binary Search Tree, where a clever ordering rule turns 'find this value among a million' into ~20 steps instead of a million.

The next ten concepts build your tree toolkit one piece at a time: what a node looks like inside, how to measure levels and height, and, most importantly, the four standard ways to WALK a tree, which power almost every tree interview problem in existence.

Node – The Building Block

A node is just a box that stores a value. Each node can store data (like 10, 'A', or 'Apple') and connect to other nodes. Think of a node as a person in a family. They have their own identity and connections to family members.

class TreeNode:
    value          # the data (10, 'A', ...)
    left  = null   # pointer to left child
    right = null   # pointer to right child

# a node with no children keeps
# both pointers as null

Open up a node: three slots, nothing more

Zoom into any circle in a tree diagram and you find a tiny record with exactly three slots: the value it stores, a pointer named left, and a pointer named right. In programming this kind of bundle is called a struct (or an object), data plus connections, packed together. That is the ENTIRE anatomy. A node does not know its parent, does not know what level it sits on, does not know it is part of something bigger. It knows its value and it holds two hands.

Take a node holding 10 whose left hand grips a node holding 5 and whose right hand grips a node holding 15. In memory that is three little boxes and two arrows, nothing else. Every tree you will ever build, no matter how huge, is this pattern repeated.

Hand-build a three-node tree, line by line

Watch the tree appear one statement at a time. After line 1 there is a single lonely node: value 10, both hands empty. Line 2 creates a second lonely node holding 5, at this moment the two are strangers; nothing connects them. Line 3 is the magic: writing a.left = b stores an arrow to b inside a's left slot. Now they form a two-node tree. Lines 4 and 5 repeat the move on the right side with 15.

Notice what 'building a tree' actually is: create nodes, then assign pointers. There is no draw_tree() call and no canvas. The picture you see in diagrams exists only in your head. The machine sees three objects and two arrows.

None is not a bug. It is the edge of the tree

After those five lines, what sits in b.left? Nothing was ever assigned, so it holds None. That is not an accident; it is information. b.left == None says, precisely: 'the node holding 5 has no left child'. Every branch of every tree ends in None. The two leaves here (5 and 15) carry four Nones between them.

This matters because every tree function you write will begin with the same guard: if node is None: return. When your code walks off the edge of the tree, it lands on None, and that guard is the floor that stops the fall. In the language of the Recursion section: None is the base case of every tree walk.

The classic mistake: hunting for the picture

Beginners often ask: 'where is the tree stored. How do I grab node number 4?' The honest answer: there is no tree[4]. Unlike an array, a tree has no indexes and no positions. Your program holds ONE variable. The root, and reaches everything else by following left/right arrows, like root.left.right. Want the node holding 15? You must walk to it.

One real source of confusion: problem sites DO print trees as arrays, like [10, 5, 15]. That is only a serialization: a flat way to TYPE a tree into a text box. Behind the scenes the judge unpacks it into real, linked TreeNode objects before calling your function. Your code never indexes; it always walks.

One extra pointer is all it takes

Compare with what you already know. An array cell stores a value and nothing else. A linked-list node stores a value plus ONE pointer (next), that buys you a chain. A tree node stores a value plus TWO pointers, and that second hand is exactly what creates branching, levels, leaves, and every algorithm in this track.

From here on, every lesson assumes this struct. The 14 tree problems ahead, from Maximum Depth of Binary Tree to Lowest Common Ancestor, all start with def solve(root) and the same three-slot TreeNode you just wired by hand.

Parent, Child, Leaf

These are the three key relationships in a tree. A PARENT is a node that connects to nodes below it. A CHILD is a node that comes from a parent above. A LEAF is a node with no children: it's at the end of a branch.

# PARENT: has at least one child
node.left != null  or  node.right != null

# LEAF: has no children at all
node.left == null  and  node.right == null

Six nodes, three job titles

Point at any node in a tree and you can hand it a job title just by looking at its arrows. Arrows going out below? It is a PARENT. An arrow coming in from above? It is a CHILD. No arrows going out at all? It is a LEAF. Run the full census on the six-node tree below: 1 is a parent (of 2 and 3) and nobody's child. Which is exactly what makes it the root. 2 and 3 are children of 1. 4 and 5 are children of 2, and 6 is the only child of 5.

Now the leaves, nodes with no children: 4, 6, and 3. Check each one: both of its pointers are empty. Every walk you can take from the root ends at one of these three nodes.

Most nodes wear both hats

'Parent' and 'child' are not exclusive clubs. Node 2 is a child (of 1) AND a parent (of 4 and 5) at the same time, like a person who is somebody's kid and somebody's dad. Node 5 pulls the same double duty: child of 2, parent of 6. In a big tree almost every node lives in this middle class; only the root skips childhood and only the leaves skip parenthood.

Nail down the edge cases while you are here: the root is the ONE node with no parent, every tree has exactly one. And 'siblings' are two children of the same parent: 2 and 3 are siblings, 4 and 5 are siblings, while 6 is an only child.

The code test for each job title

Your program checks a node's title in one line, using only the two pointers from the last concept. A node is a parent if AT LEAST one hand is full; a leaf if BOTH hands are empty. Watch the and/or difference, it is easy to flip and painful to debug: 'or' asks whether ANY child exists, 'and' demands that BOTH slots be empty.

One asymmetry worth noticing: a node can inspect its children (they sit right there in .left and .right) but it cannot name its own parent, TreeNode stores no upward pointer. Information flows down. When an algorithm needs parents, it must remember them on the way down; you will see that trick in Lowest Common Ancestor.

Why leaves matter: every recursion lands on them

Leaves look unimportant, nothing hangs below them. But they are where every tree computation bottoms out. Compute a height, count nodes, sum values, hunt for a path: the recursive calls dive until they reach the leaves (and the Nones just past them), turn around, and pass answers back up. Leaves are the ground floor the whole answer is stacked on.

You will feel this immediately in the lessons: in Maximum Depth of Binary Tree the count starts at the leaves; in Path Sum the question 'did we hit the target?' is only ever DECIDED at a leaf. Whenever you design a tree recursion, your first question should be: what happens at a leaf?

The trap: 'leaf' is about children, not about depth

The most common beginner slip: assuming all leaves live on the bottom row of the picture. Look at node 3. It sits high (one step below the root, on the same floor as 2) and yet it IS a leaf, because both of its pointers are empty. Meanwhile 6, the deepest node, is also a leaf. Leaves can appear on ANY level; the drawing's bottom row has nothing to do with it.

The only test that counts is the code test: node.left is None and node.right is None. So when a problem says 'root-to-leaf path' (Path Sum, coming up), the short walk 1→3 fully counts: it truly ends at a leaf.

Levels in a Tree

Each horizontal layer in a tree is called a LEVEL. The root is at Level 0. Its children are at Level 1. Their children are at Level 2, and so on. The level number equals the distance from the root!

level(root)  = 0
level(child) = level(parent) + 1

# a node's level = number of steps
# from the root down to that node

A tree is a building: floors, not positions

Group the nodes below by how many steps they sit from the root and the tree resolves into clean horizontal floors. Node 1 is 0 steps away: Level 0. Nodes 2 and 3 are one step away: Level 1. Nodes 4, 5 and 6 are two steps away: Level 2. That number, steps from the root, is the node's level, and every node has exactly one, because a tree has exactly one path from the root to anywhere (the one-path law from the first concept).

The root is ALWAYS Level 0 no matter how the tree is drawn, and a child's level is always its parent's level plus one. That is the entire arithmetic of levels.

Count a level with a pencil

To find node 6's level, walk the only path from the root and count edges: 1→3 is step one, 3→6 is step two. Two steps: Level 2. Now node 4: 1→2, then 2→4, also Level 2. Notice that 4 and 6 are distant relatives (different parents, different grandparents: cousins at best), yet they share a floor. Level ignores family lines; it only measures distance from the top.

Group the whole tree this way and you get the floor plan below. Keep its exact shape in mind ([[1], [2, 3], [4, 5, 6]]) because a whole family of interview problems asks you to return the tree in precisely this form.

Where levels come from in code: BFS rings

Nothing inside a TreeNode stores its level. There is no node.level slot. So where does the number come from? From HOW you walk. Process the tree one ring at a time: start holding just the root ([1]), then collect all children of that ring ([2, 3]), then all THEIR children ([4, 5, 6]). Each ring you hold is exactly one level, and a counter you bump once per ring is the level number.

Trace the loop: ring starts as [1] with level = 0; the for-loop visits 1 and gathers 2 and 3; ring becomes [2, 3] and level becomes 1; the next pass gathers 4 and 5 from node 2 and 6 from node 3; ring becomes [4, 5, 6] with level 2; then the ring comes up empty and the loop ends. The level was never stored anywhere: it EMERGED from walking floor by floor.

The off-by-one to watch for

Two counting conventions live in the wild, and mixing them is a classic source of wrong answers. This course (and most code) starts at Level 0: level equals edges from the root. Some textbooks start the root at Level 1. Neither is wrong, but you must know which one a problem means: our tree has floors 0, 1, 2. That is THREE levels total, while the deepest level INDEX is 2. Asked 'how many levels?', answer 3; asked 'what is the deepest level?', in 0-based terms the answer is 2.

A related slip: assuming nodes drawn at the same height in a picture share a level. Diagrams can be stretched or slanted; the only truth is the edge count from the root. Count steps, never eyeball pixels.

Levels power a whole family of problems

The ring-by-ring walk you just traced has a famous name, Breadth-First Search, and it is the entire engine of the Level Order Traversal concept at the end of this page, where the ring becomes an explicit queue. The lesson track then leans on it hard: Binary Tree Level Order Traversal literally returns the floor plan [[1], [2, 3], [4, 5, 6]], and the popular right-side-view and zigzag interview variants are one-line tweaks of the same loop.

Levels also travel beyond trees: in the Graphs track, BFS rings from a start cell give shortest distances, Rotting Oranges spreads rot exactly one ring per minute. Learn the ring picture once and you will reuse it everywhere.

Height of a Tree

Height of a tree = the number of edges from the root to the deepest leaf. Important: Height is measured DOWNWARDS, and only the LONGEST path matters. If there are multiple paths to different leaves, we count the longest one.

height(null) = 0        # empty spot

height(node) = 1 + max(height(node.left),
                       height(node.right))

# yourself, plus your TALLER subtree

How tall is this tree? Count edges on the LONGEST walk

Height answers one question: starting at the root, how far DOWN can you possibly walk? Take the six-node tree below (the same one from Parent, Child, Leaf) and list every root-to-leaf walk: 1→2→4 uses 2 edges; 1→2→5→6 uses 3 edges; 1→3 uses just 1. The height of the tree is the longest of these: 3. Short branches do not vote; only the deepest walk defines the height.

That is why the definition says edges on the LONGEST root-to-leaf path. A tree with a thousand short branches and one long one is exactly as tall as that one long branch.

Compute it bottom-up, leaf by leaf

Nobody measures a big tree by re-walking every path from the root. You build heights UP from the leaves, each node asking only its children. Every leaf has height 0. No edges below it, so mark 4, 6 and 3 with h=0. Any parent's height is then 1 + the taller of its children. Node 5: its only child 6 has h=0, so h(5) = 1. Node 2: children score h=0 (node 4) and h=1 (node 5); take the max and add one: h(2) = 2. The root: children score h=2 and h=0, so h(1) = 3, matching the walk we counted by hand.

Feel the direction: LEVELS were computed top-down (steps from the root). HEIGHT is computed bottom-up (answers rise from the leaves). This bottom-up flow is precisely the postorder pattern you will meet three concepts from now.

The code, and which ruler it uses

Here is the recursion in two flavors, and this is THE subtlety of the concept. The pattern from the pseudo-code panel above (empty spot returns 0, node returns 1 + max of children) actually counts NODES on the longest path: run it on our tree and a leaf returns 1 + max(0, 0) = 1, node 5 returns 2, node 2 returns 3, and the root returns 4, because the path 1→2→5→6 has 4 nodes and 3 edges. Both rulers are legitimate and both appear in real problems: LeetCode's Maximum Depth of Binary Tree wants the node count (4 here), while the edge-counting definition of height gives 3, always exactly one less.

To make the same recursion count edges, change one tiny thing: let the empty spot return -1 instead of 0. Then a leaf computes 1 + max(-1, -1) = 0 and the root lands on 3. Same shape, different base case: you pick the base case to pick the ruler.

Height vs depth: opposite arrows

Height and depth get confused because both measure 'how far', but they point in opposite directions. DEPTH of a node = edges from the ROOT down to it, measured from the top; it is the same number as the node's level. HEIGHT of a node = edges from that node down to its DEEPEST descendant leaf, measured from the bottom. Check node 5: depth 2 (walk 1→2→5), height 1 (walk 5→6). Node 2: depth 1, height 2. The root always has depth 0, and its height IS the height of the whole tree.

Memory hook: depth is how far you have FALLEN from the root; height is how much tree still stands UNDER you. A node deep in the tree has a big depth and a small height.

Why height is everywhere

Height is the first real recursion of this track and the template for half the problems in it. Maximum Depth of Binary Tree IS the height_nodes function, line for line. Your first tree lesson is already written in your head. Diameter of Binary Tree computes left and right heights at every node and adds them. Balanced-tree checks compare children's heights. Height even controls COST: the call stack during any tree recursion grows to about the tree's height, which is why a skewed chain of n nodes (height n-1) recurses dangerously deep while a bushy, balanced tree keeps height near log n.

Binary Tree

A Binary Tree is the most common type of tree in programming. It has one simple rule: each node can have AT MOST 2 children. They are specifically called the LEFT child and RIGHT child. This '2 children max' rule is what makes binary trees so useful for algorithms!

class TreeNode:
    value
    left     # at most TWO children:
    right    # left and right, never a third

One rule changes everything: at most two children

A general tree puts no limit on children. A folder can hold fifty files; a manager can have nine reports. Node A below has three children, and as a TREE that is perfectly legal. A BINARY tree adds one strict rule: every node has AT MOST two children, each with a fixed name, left or right. Zero children is fine (that is a leaf), one is fine, two is fine. Three is forbidden.

The diagram breaks the rule at exactly one node: A holds B, C and D. For this structure to live in binary-tree world, one of those three arrows has to go.

Why two? Because named slots make recursion trivial

The magic is not the number two. It is that both slots have NAMES. A general tree stores 'a list of children', so every algorithm needs a loop: for child in node.children. A binary tree stores exactly node.left and node.right, so every algorithm becomes two clean lines. Solve(node.left), solve(node.right), then combine. All four traversals you are about to learn, and all 14 tree lessons in this track, are built from those two named calls.

The names also make EMPTY slots meaningful. 'A node whose only child hangs left' and 'a node whose only child hangs right' are two DIFFERENT trees, compare below. A general tree with a one-item child list cannot even express that difference. Left versus right is real information: it is the entire subject of the Invert Binary Tree and Symmetric Tree lessons.

The final form of TreeNode

This is the struct from Node. The Building Block, now official: value, left, right, nothing else. Every problem in this track hands you nodes of exactly this shape, and it is (down to the spelling) the definition LeetCode pastes into every tree problem. With at most two pointers, a node can only ever be in four configurations: no children (a leaf), left-only, right-only, or both.

Any tree can be rebuilt as a binary tree

Worried that 'at most two' is too weak for the real world of fifty-file folders? A classic trick (left-child, right-sibling) rebuilds ANY tree using only two pointers per node: point each node's LEFT at its first child, and each node's RIGHT at its next sibling. A's three children B, C, D become: A's left is B, B's right is C, C's right is D. Every parent-child fact survives; two pointers were enough all along.

You will not need this trick in the lessons ahead: every problem hands you a binary tree directly. But it explains why binary trees get all the attention: they are not a special case; they are a universal representation.

Coming attraction: add an ordering rule, get a search machine

One more reason binary trees dominate interviews: give the two slots a MEANING and you unlock new powers. The Binary Search Tree (BST) adds a single rule, everything in a node's left subtree is smaller than the node, everything in its right subtree is bigger. That rule turns 'find value x' into a guided walk: compare at each node, step left or right, and discard half of the remaining tree at every step, roughly 20 comparisons to search a million items.

The rule itself is a later lesson (Validate Binary Search Tree makes you enforce it precisely), and the Inorder Traversal concept on this page will show you its most famous side effect. For now, lock in today's rule: two named slots, never a third.

Tree Traversal

Traversal means 'visiting every node in a tree'. Just like reading a book: different reading orders give different meanings. In trees, we have 4 main ways to visit all nodes, each useful for different problems.

# a traversal = a RULE for visiting order
traverse(node):
    visit(node)           # 'do something'
    traverse(node.left)   # walk the branches
    traverse(node.right)

# moving the visit line = a new traversal!

Six nodes to visit, but who goes second?

An array forces an order on you: index 0, then 1, then 2. A tree does not. Stand at root 1 below: you could speak its name first, or dive left first, or handle the whole left side before even glancing right. After node 2, do you go down to 4 or across to 5? Every choice is defensible, so computer science standardized a few visiting RULES, called traversals, and nearly every tree problem is secretly one of them plus a little work done at each visit.

Get this straight now and the next four concepts become easy: a traversal is not a new data structure and not magic. It is just an agreed-upon answer to the question 'who goes next?'.

Four rules, four sequences: same six nodes

Here is the whole menu, run on the one tree above. Three rules are depth-first (DFS): they dive down a branch as far as possible before backing up, and they differ ONLY in when the node in the middle speaks, before its children (preorder), between them (inorder), or after them (postorder). The fourth is breadth-first (BFS): sweep floor by floor, exactly the levels you met two concepts ago.

Read the four outputs and notice how different they are. The root 1 speaks first in preorder, fourth in inorder, dead last in postorder, first again in level order. Six nodes, four different sentences: the rule you pick changes the story the tree tells.

The dirty secret: the three DFS orders are ONE function

Write the recursion once: guard against None, recurse left, recurse right. Now ask. Where does the visit line go? Put it BEFORE the two calls: preorder. Squeeze it BETWEEN them: inorder. Drop it AFTER both: postorder. Three famous algorithms, one line sliding up and down. In the next three concepts you are not learning three programs. You are learning three positions of one line.

This is also why the DFS trio all cost the same: each visits every node exactly once, whatever the position of the visit line. What changes is not the work. It is the ORDER the results come out in.

Does the order actually matter? Copy vs delete

Order sounds cosmetic until the job constrains it. COPYING a tree: you must create a parent node before you can attach children to it. The root must be handled FIRST, so copying is preorder work. DELETING a tree in a manual-memory language: free a parent first and you lose your only pointers to its children. Children must go FIRST and the root LAST, so deletion is postorder work. Reading a Binary Search Tree in SORTED order: only the middle position works, inorder. Printing the org chart floor by floor for your boss: level order.

Same tree, same six nodes, but pick the wrong order for the job and the algorithm is not merely slower, it is WRONG. That is why interviewers care whether you know which order fits which task.

Your roadmap for the next four concepts

Each of the next four concepts takes one row of that table and slows it down: a pencil-and-paper walk producing the exact sequence, the code with the visit line in position, and the jobs the order is built for. They are not just theory. The opening lessons of this track ARE these traversals as graded problems: Binary Tree Preorder Traversal, Inorder, Postorder, and Binary Tree Level Order Traversal.

And they keep paying rent afterwards: Maximum Depth and Diameter of Binary Tree are postorder thinking (children report, parent combines), Validate Binary Search Tree leans on inorder, and Construct Binary Tree from Preorder and Inorder Traversal uses two orders at once to rebuild a tree. Learn the four rules once; the rest of the track is applications.

Preorder Traversal

Preorder visits nodes in this order: ROOT first, then LEFT subtree, then RIGHT subtree. Think of it as 'visit yourself BEFORE your children'. This is useful for copying trees or creating prefix expressions.

preorder(node):
    if node == null: return
    visit(node)            # 1. ROOT first
    preorder(node.left)    # 2. then LEFT
    preorder(node.right)   # 3. then RIGHT

Rule: speak first, then visit your children

Preorder is the boss-first order: a node announces itself BEFORE either child gets a turn. Root, then the entire left subtree, then the entire right subtree. Think of a manager introducing her org: 'I am 1. Here is my left team… and here is my right team.' The same etiquette applies at every node, all the way down.

One consequence you can bank on forever: the FIRST value a preorder prints is always the root of the tree. Interviewers build whole problems on that single fact. Construct Binary Tree from Preorder and Inorder Traversal starts by reading preorder[0] and declaring it the root.

Hand-walk it: pencil down, follow along

Start at 1, speak immediately: 1. The rule says finish the ENTIRE left side before glancing right. Step to 2, speak: 2. Left again to 4, speak: 4. Node 4 is a leaf, so backtrack to 2 and take its right child: 5, speak: 5. That completes 2's whole subtree, so backtrack to 1 and go right: 3, speak: 3. Node 3 has no left child, so take its right: 6, speak: 6. Final sequence: 1, 2, 4, 5, 3, 6.

Self-check trick for any drawing: trace the outline of the tree counterclockwise starting just left of the root, and write down each node the FIRST time your pencil touches it (passing its left side). That finger-trace produces preorder every time.

The code: the visit line sits on TOP

Three working lines. The None-guard floors the recursion: it fires at every missing child, like 4's empty hands. Then look at WHERE visit(node) sits: first, above both recursive calls. That single position is the entire definition of preorder. Slide that line down one slot and you would have inorder; drop it to the bottom, postorder. Nothing else changes.

Match the code to your hand-walk: visit(1) runs before preorder(node.left) even starts. Which is why 1 led the sequence, and why 2 printed before either 4 or 5.

What preorder is for: copying and saving trees

Preorder hands you nodes in 'buildable' order: every parent arrives before its children. That is exactly what copying needs: you cannot attach a child to a parent that does not exist yet. The clone function below IS a preorder: create the fresh parent (that is the visit), then recurse to build and attach its children.

The same idea powers serialization: walk preorder, write each value (plus markers for the Nones), and you can stream a tree into a file or across a network, then rebuild it identically on the other side. Root-first order means the rebuilder always knows the parent before it meets the children.

The classic slips

Slip #1: forgetting the None-guard. The first missing child you recurse into (node 4's empty left) explodes with 'NoneType' has no attribute 'val'. The guard is not decoration; it is the floor. Slip #2: swapping the two recursive calls. Walk right before left on our tree and you print 1, 3, 6, 2, 5, 4. A plausible-looking sequence that is simply not preorder. The order of the calls is part of the definition. Slip #3: believing preorder alone can rebuild the tree. It cannot: 1, 2, 4, 5, 3, 6 fits several different shapes, unless you also record the Nones, or pair it with a second traversal, which is precisely the trick in Construct Binary Tree from Preorder and Inorder Traversal.

Inorder Traversal

Inorder visits nodes in this order: LEFT subtree first, then ROOT, then RIGHT subtree. The root is visited IN the middle. This traversal is very important in Binary Search Trees. It gives you values in sorted order!

inorder(node):
    if node == null: return
    inorder(node.left)     # 1. LEFT first
    visit(node)            # 2. ROOT in the middle
    inorder(node.right)    # 3. then RIGHT

Rule: left arm, then you, then right arm

Inorder makes each node speak in the MIDDLE: finish the entire left subtree, then visit the node, then the entire right subtree. Surprising consequence: the root does NOT go first. On the tree below the first voice is 4, the leftmost node, because from 1 you slide left to 2, keep sliding to 4, and only when there is no more left do you finally speak.

So the mental habit for inorder is: drive left until you hit the wall, then start reading on the way back. The root waits for the middle of the output; the leftmost node always opens, and the rightmost always closes.

Hand-walk it to 4, 2, 5, 1, 3, 6

At 1: do NOT speak, the left side goes first. At 2: still silent; it has a left child too. At 4: no left child, so NOW speak: 4. Back up to 2: its left side is finished, so 2 speaks: 4, 2. Then 2's right side: 5 has no left child, so it speaks: 4, 2, 5. That closes 1's entire left subtree, so 1 finally speaks: 4, 2, 5, 1. The right side runs the same way: 3 has no left child, so 3 speaks, then its right child 6. Full sequence: 4, 2, 5, 1, 3, 6.

Self-check trick: let the sun shine straight down and read the nodes' SHADOWS from left to right across the page, 4 is leftmost, then 2, 5, 1, 3, 6. In these diagrams horizontal position matches inorder position, which is why inorder is often called the left-to-right reading of a tree.

The code: the visit line moves to the MIDDLE

Same three working lines as preorder: the visit line simply slid down one slot, in between the recursive calls. That one move changes everything: now no node may speak until its whole left subtree has finished. Match it against your walk: inorder(2) ran inorder(4) to completion (printing 4) BEFORE the visit line let 2 speak, and 1 had to wait for all of 4, 2, 5.

The killer feature: sorted output from a BST

Here is why inorder is famous. Recall the Binary Search Tree rule teased in the Binary Tree concept: left subtree smaller, right subtree bigger. Run inorder on such a tree and watch what the order guarantees: everything smaller than a node prints before it, everything bigger prints after. Applied recursively at every node, the values come out in fully SORTED ascending order, every time. The BST below stores 1 through 7 scattered across three levels; inorder reads them out as 1, 2, 3, 4, 5, 6, 7 without a single comparison.

This one fact powers the Validate Binary Search Tree lesson. A tree is a valid BST exactly when its inorder comes out strictly increasing, and every 'k-th smallest in a BST' problem: the k-th value inorder visits IS the k-th smallest.

The trap: inorder is NOT sorted on an ordinary tree

Do not overlearn the last section. Sorted output is a property of BST + inorder TOGETHER, not of inorder alone. Our practice tree gave 4, 2, 5, 1, 3, 6, nowhere near sorted, and nothing went wrong: that tree simply is not a BST, so its left-to-right reading has no reason to be ordered. If a problem does not guarantee a BST, never assume inorder means sorted.

Second slip: 'go left first' does not mean 'visit the root's left CHILD first'. It means drive to the leftmost DESCENDANT first. The first voice is the bottom of the left spine (4), not the left child (2). And even on plain trees inorder earns its keep: in Construct Binary Tree from Preorder and Inorder Traversal, the inorder sequence is what tells you which nodes lie to the left versus the right of the root.

Postorder Traversal

Postorder visits nodes in this order: LEFT subtree first, then RIGHT subtree, then ROOT last. Think of it as 'visit yourself AFTER your children'. This is useful for deleting trees or calculating sizes from the bottom up.

postorder(node):
    if node == null: return
    postorder(node.left)   # 1. LEFT first
    postorder(node.right)  # 2. then RIGHT
    visit(node)            # 3. ROOT last

Rule: children report before the parent

Postorder is the bottom-up order: a node speaks only AFTER both of its subtrees are completely finished. Left subtree, right subtree, then the node itself. Picture a manager who can only file her report after every member of her team has filed theirs; apply that at every node and the big boss (the root) files dead last.

Two facts you can bank on: the FIRST voice in a postorder is the leftmost leaf (4 below. Deepest on the left, nothing under it), and the LAST voice is ALWAYS the root. That last-is-root fact mirrors preorder's first-is-root, and tree-reconstruction problems exploit both ends.

Hand-walk it to 4, 5, 2, 6, 3, 1

At 1: silent, both subtrees must finish first. At 2: silent for the same reason. At 4: it is a leaf, its (empty) subtrees are trivially done, speak: 4. Back at 2: the left is done but the right is not. Go to 5, a leaf, speak: 5. NOW both of 2's subtrees are complete, so 2 speaks: 4, 5, 2. Over on the right: 3 stays silent (its right subtree is pending), 6 is a leaf, speak: 6. Now 3 can speak, and finally, with both of its subtrees complete, 1. Full order: 4, 5, 2, 6, 3, 1.

Feel the rhythm: you DESCEND silently, and a name is only spoken on the way back UP, postorder tags each node at the last moment you ever stand on it. Preorder tags on arrival; postorder tags on final departure.

The code: the visit line sinks to the BOTTOM

The visit line completes its journey: below both recursive calls. Read it against the walk: postorder(2) first drains postorder(4) (printing 4) and postorder(5) (printing 5); only then does the visit line finally run for 2. Nothing else has changed since preorder. The three DFS orders really are one function with a sliding line, and this is the line's final resting place.

What postorder is for: answers that must flow bottom-up

Reach for postorder whenever a parent's answer DEPENDS on its children's answers. Size of a tree: node 2 cannot say 'my team is 3' until node 4 reports 1 and node 5 reports 1. Children first, then combine, which IS postorder. Trace it: size(4)=1 and size(5)=1 give size(2)=1+1+1=3; size(6)=1 gives size(3)=2; the root totals 1+3+2=6. Height worked exactly the same way back in the Height concept. Leaves said 0, parents combined upward. Same skeleton, different combine line.

Deletion is the other classic: in a manual-memory language you must free the children before the parent, because freeing the parent destroys your only pointers to its children, sawing off the branch you are sitting on. Postorder is the only safe demolition order.

The classic slips

Slip #1: doing bottom-up work in top-down order. Delete or total the parent BEFORE the children and you either lose the children entirely (freed parent = lost pointers) or you combine numbers that do not exist yet. The test is simple: if the parent needs the children's results, the visit line must come last. Slip #2: assuming postorder is preorder reversed. Reverse our preorder 1, 2, 4, 5, 3, 6 and you get 6, 3, 5, 4, 2, 1, but the true postorder is 4, 5, 2, 6, 3, 1. (Reversed preorder only matches postorder if you ALSO swap every left and right.) Slip #3: missing the free gift. Postorder's last element is always the root, just as preorder's first is; reconstruction problems read roots off those two ends.

Level Order Traversal

Level Order visits nodes level by level, from left to right. It finishes one entire level before moving to the next. This uses a Queue (FIFO) internally. Nodes 'wait in line' to be visited.

levelOrder(root):
    queue = [root]
    while queue is not empty:
        node = queue.pop_front()
        visit(node)
        if node.left:  queue.push(node.left)
        if node.right: queue.push(node.right)

Read the tree like a book: floor by floor

The three DFS orders dive: they run down a branch all the way to a leaf before backing up. Level order refuses to dive. It reads the tree the way you read a page: top floor first, left to right, then the next floor down: 1, then 2, 3, then 4, 5, 6. These are exactly the floors from the Levels concept, visited in order.

But notice: recursion will not naturally produce this. A recursive call plunges to node 4 long before it ever reaches 3. Sweeping across floors needs a different engine: a QUEUE, the waiting line from the Queues section (this is why it sits on this page's prerequisite banner). Nodes stand in line; first in, first out; children join at the back.

The queue, snapshot by snapshot

Run it slowly. The queue starts holding just the root: [1]. Pop the front: visit 1, and push its children at the back: [2, 3]. Pop 2, visit it, push 4 and 5: [3, 4, 5]. Pop 3, visit it, push 6: [4, 5, 6]. Freeze right there and look at what the line holds the instant floor 1 finishes: exactly [4, 5, 6], which is exactly Level 2. That is the whole magic: parents on floor k push their children BEHIND everything remaining from floor k, so the line drains one full floor before the next floor begins.

Finish the run: pop 4 (a leaf, nothing to push), pop 5, pop 6, and the empty queue ends the show. Total visit order: 1, 2, 3, 4, 5, 6.

The code: a loop and a line, no recursion

This is the pseudo-code from the panel above as runnable Python. Two details carry all the weight: popleft() takes from the FRONT of the line (first in, first out), and the two appends put children at the BACK. The if-guards keep None out of the line: push a None and a later popleft hands it back, and visiting it crashes on None.val.

Map it to the snapshots: the while loop ran six times, once per node, and every append happened exactly when you pictured a child joining the line.

The level-size trick: draw the floor boundaries

The plain loop prints 1, 2, 3, 4, 5, 6 as one stream: it never says where a floor ends. Most real problems want the floors SEPARATED: [[1], [2, 3], [4, 5, 6]]. The trick: at the instant a floor is about to start, len(queue) is EXACTLY the number of nodes on that floor. You saw it, the queue held precisely [4, 5, 6] as floor 2 began. So freeze that number and pop exactly that many nodes into one group; everything their children pushed behind them is the NEXT floor.

On our tree the frozen sizes go 1, then 2, then 3, producing the groups [1], [2, 3], [4, 5, 6]. This exact loop is the engine of the Binary Tree Level Order Traversal lesson, and the popular zigzag and right-side-view interview variants are one-line decorations of it.

The trap: grab the wrong end and BFS becomes DFS

One character can flip the algorithm's family. In Python, list.pop() removes from the RIGHT end: the same end the appends feed. Do that and your 'line' is actually a STACK: last in, first out. Trace it on our tree: [1] → pop 1, push 2, 3 → [2, 3] → pop 3 (the back!), push 6 → [2, 6] → pop 6 → [2] → pop 2, push 4, 5 → pop 5 → pop 4. Visit order: 1, 3, 6, 2, 5, 4, a depth-first dive down the right side, not level order at all. The code LOOKS almost identical; only the end you pop from is wrong.

So: queue + popleft = BFS floors; stack + pop = DFS dives. Both are useful, but they answer different questions, and mixing them up is THE classic level-order bug. Two smaller traps: skipping the if-guards (a None sneaks into the line and crashes the visit), and touching the queue before handling an empty tree (root is None).

All DSA learning paths