Tree terms and traversals in Python

Why this lesson matters

A tree is one of the most useful shapes a program can store data in. File folders on your computer are a tree. The page you are reading is stored in the browser as a tree of HTML elements. A search engine's index, a compiler's view of your code and a chess program's list of possible moves all use trees. Almost every tree problem you will meet in a job interview starts with the same question: in what order should I visit the nodes?

This lesson gives you the vocabulary, the Python class for a tree node, and the three basic ways to walk through a tree. By the end you will be able to build a small tree in code, print its nodes in three orders, and explain why each order does what it does. You will also see the same walk done without recursion, using a list as a stack, because interviewers often ask for both versions.

You do not need to know anything about trees yet. You should be comfortable with functions, classes and lists from the earlier Python modules. If the word None still feels strange, read the next section before you go on.

The idea of a tree

Start with something you already know. A family tree is a drawing of a family. The oldest ancestor sits at the top. Below them are their children, and below those are their grandchildren. Each line on the drawing goes down from a parent to a child, never sideways and never back up.

A tree in programming is a collection of nodes. A node is a small box that holds a value and points to other nodes. The boxes are connected by edges, the lines between them. Two rules make a structure a tree:

• There is exactly one top node, called the root. It has no parent.
• Every other node has exactly one parent, the node directly above it.

Because of these rules, a tree never loops back on itself. If you start at any node and follow the edges downward, you can never return to a node you already passed. That property is what makes trees easy to reason about. A tree with n nodes always has exactly n - 1 edges, because every node except the root uses one edge to connect to its parent.

Here is a tree with six nodes, drawn the way programmers draw it, with the root at the top:

        1
       / \
      2   3
     / \   \
    4   5   6

We will use this tree in almost every example in this lesson and the next one, so it is worth learning to read it now.

The words you need

Each of these terms has a plain meaning. Read them slowly once, then use the tree above to check each one.

• Root: the top node. In the tree above, the root is 1.
• Parent: the node directly above another node. The parent of 5 is 2.
• Child: a node directly below another. The children of 2 are 4 and 5.
• Sibling: two nodes with the same parent. 4 and 5 are siblings.
• Leaf: a node with no children. The leaves in the tree above are 4, 5 and 6.
• Internal node: any node that has at least one child. Here that is 1, 2 and 3.
• Subtree: a node together with all the nodes below it. The subtree rooted at 3 holds 3 and 6.
• Depth of a node: the number of edges you cross to reach it from the root. The root has depth 0. Node 5 has depth 2.
• Level: all nodes at the same depth. Level 0 holds 1, level 1 holds 2 and 3, and level 2 holds 4, 5 and 6. Some books start levels at 1. This course starts at 0 for depth and says "level 1" when it means the top row.
• Height of a tree: the length of the longest path from the root down to a leaf. This course counts height in nodes, so a tree with only the root has height 1, and an empty tree has height 0. The next lesson is about height in detail.

A binary tree is a tree in which each node has at most two children. They are called left and right. A node can have one child, two children or none. The word "binary" means "two", and the two children are not interchangeable: 2 is the left child of 1 and 3 is the right child, and swapping them makes a different tree.

Nodes with one child need care. In the tree above, node 3 has no left child and one right child, 6. We say its left child is missing. In Python, a missing child is stored as None.

What None means

None is Python's word for "no object here". A variable such as node.left holds a reference to another object. A reference is a way to reach an object, similar to an address written on a slip of paper. When there is no object, the reference holds None. Think of it as an empty box with nothing written on it.

This matters because you cannot ask an object for its attributes if the reference is None. If you write left.val while left is None, Python stops the program with an AttributeError. Almost every bug in tree code is a missing None check. The rule you will follow throughout this module is simple: before you touch a node, check that it is not None. Use is None for that check, because is asks whether two names point at the same object, and None is only one object.

The node in Python

In Python, a tree node is a class with three attributes: a value, a left child and a right child. Here it is:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

A few things are worth noticing.

• self.val holds the number stored in the node. You could store a string or any other object, but numbers keep the examples short.
• self.left and self.right start as None. The constructor sets them, so a new node is a leaf until you attach children to it.
• self is the node itself. Inside the constructor, self.val = val stores the value you passed in as an attribute of the new object.

Python does not have a separate type for a reference. Every name in Python is a label that points to an object, and self.left is simply an attribute that points to another TreeNode or to None. Python also does not check the type of an attribute when you assign it. A mistake such as putting a string in left will not fail until the code tries to use it, so a type checker, a tool that reads code for wrong types, can catch such mistakes early.

What happens in memory

When you write TreeNode(1), Python creates one object in memory. That object has room for val, left and right. The name root points to it. When you then write root.left = TreeNode(2), Python creates a second object and stores a reference to it in the left attribute of the first. No node is inside another node. Each node is a separate object, and the links between them are references.

Picture six separate boxes in memory, each holding a value and two references. The references are the arrows from one box to another. A reference that points nowhere holds None, which is the missing child. Keep this picture in mind. Every tree algorithm in this module follows references from one object to the next, and it is much easier to reason about if you can picture the objects.

Building a tree by hand

Here is the code that builds the six-node tree. It creates each node by calling TreeNode and connects it with an assignment. Read it line by line, because you will write code like this in every lesson of the module.

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

Read root.left.left as "start at the root, go to its left child, then go to that node's left child". Each dot follows one reference. This is the same walk you would do by eye on the drawing. Once the tree is built, the name root is the only handle you need. Every other node is reachable from it.

Building trees by hand is fine for six nodes. It is tedious for sixty, and it is impossible to do for input that arrives while the program runs. Later in this lesson you will see a function that builds a tree from a list of values, and the module assignment uses it. For now, the hand-built tree gives us something fixed to test against.

Recursion: the tool for trees

Trees and recursion fit together. A recursive function is one that calls itself. For a tree, the rule is:

• The answer for a node depends on the answers for its two children, plus whatever the node itself contributes.
• The answer for None is a fixed value, which is the base case.

Here is an everyday comparison. Suppose a teacher wants to know how many students are in a row of desks, but she can only ask the student in front of her. She asks the front student, "how many are behind you, including you?" That student asks the next one, and so on, until the last student says "one, just me". The answers come back down the line, each student adding one. A tree works the same way. Each node asks its children for their counts and adds itself.

The base case is what stops the chain. For a tree, the base case is "there is no node here", which is None. Calling a method on None is the same as asking an empty chair. Every recursive tree function starts with a check for None and returns immediately when it finds one.

Every call to a function takes a small amount of memory to remember where to return and what its local variables hold. This memory lives in the call stack, which is a stack of frames, one per active call. You will see this stack in action in the traversal examples below. It is also the reason a tree's depth limits how much memory a recursive function uses.

Step through the animation above and watch the frames pile up as the walk goes down the left side, and then unwind as each call returns. Notice that the stack never holds more frames than the deepest path from the root to a leaf.

The three depth-first traversals

A traversal is a walk that visits every node exactly once. Trees have many possible walks, but the most useful family is the depth-first walk. It goes as far down one branch as it can before it comes back to try the next branch. Each depth-first walk has the same shape: it visits the current node, the left subtree and the right subtree. The only thing that changes is when the current node is visited.

• Preorder: visit the node, then the left subtree, then the right subtree. Node, left, right.
• Inorder: visit the left subtree, then the node, then the right subtree. Left, node, right.
• Postorder: visit the left subtree, then the right subtree, then the node. Left, right, node.

The word before "order" tells you where the node goes. "Pre" means before the children, "in" means between them, and "post" means after them. If you remember that one rule, you never need to memorise the other two lists.

Here is the code for all three, plus a block at the bottom that prints the results for the six-node tree. Each function takes a list named out and adds each value to it with append. Printing the list at the end gives square brackets with commas between the values, which is the format the examples below use.

Run it. The output is:

preorder:  [1, 2, 4, 5, 3, 6]
inorder:   [4, 2, 5, 1, 3, 6]
postorder: [4, 5, 2, 6, 3, 1]

Each function has the same three-part body: a None check, then two recursive calls, with the append line placed before, between or after them. The only difference between the three functions is where that one append line sits. That is the whole idea of the three orders, written in code.

Tracing the preorder call by call

Reading output is not enough. To understand a recursive function, trace what it does, one call at a time. Here is the start of the trace for preorder(root, out).

1. Call preorder(1). The node is not None. Append 1. Now call the left child.
2. Call preorder(2). Not None. Append 2. Call its left child.
3. Call preorder(4). Not None. Append 4. Call its left child, which is None.
4. Call preorder(None). It returns at once. Back in node 4, call its right child.
5. Call preorder(None) again. It returns. Node 4 has finished, so return to node 2.
6. Back in node 2, call its right child, which is 5. Append 5. Both of its children are None, so 5 returns.
7. Node 2 has finished. Return to node 1 and call its right child, 3.
8. Node 3 appends 3, skips its missing left child, and calls its right child, 6.
9. Node 6 appends 6, and both its children are None. The walk is finished.

The list now holds 1, 2, 4, 5, 3, 6, the same as the output. Notice how many None calls happen. There are seven missing child slots in a six-node tree, and each one makes a call that returns at once. That is normal: a tree with n nodes has n + 1 empty slots, counting the two empty slots of each leaf and the missing slots of the other nodes. The total work is still proportional to n.

Why the orders differ

Each order is useful for a different reason.

Preorder visits a parent before its children. That means you can create or print a parent before you look at anything below it. If you copy a tree, you create the copy of the root first, then copy the left and right subtrees and attach them. The preorder list is also the easiest way to write a tree to a file: you write the parent, then the children.

Inorder on a binary search tree gives the values in sorted order. The next module explains why. For a general binary tree, inorder is useful when the left and right subtrees are read as a sequence with the node in the middle, such as the operands and operator of a math expression.

Postorder visits the children before the parent. That is exactly what you need when a parent's answer depends on its children's answers, and when you want to free or delete the children first. Suppose you want the size of every subtree. You cannot finish a node until both children are done, so postorder is the natural order.

The table below summarises the three orders for the six-node tree.

Use the animation above to step through the three orders on this tree. Watch which node is marked as visited at each step, and notice that the visit happens at a different point in the walk for each order.

Iterative inorder: the same walk with a stack

Recursion is elegant, but it has a limit. Each call uses a frame on the call stack, and Python stops a recursive chain once it gets too deep. A tree that is one long chain of 2,000 nodes would need 2,000 frames, which is more than Python allows by default. Interviewers often ask you to write the traversal without recursion, so that you use an explicit stack instead. The stack is a list that you control, and it can hold as many items as your memory allows.

A stack is a last-in, first-out collection. You push an item on top and pop the top item off. In Python, a plain list does this job well: stack.append(item) pushes, and stack.pop() removes and returns the last item. Both run in constant time on average, so the time does not depend on how long the list is.

The inorder version works like this. Walk left as far as you can, pushing each node you pass. When you cannot go further left, pop the last pushed node, visit it, and then move to its right child. Repeat until there are no nodes left to push and the stack is empty.

Here is the code. It returns the list instead of filling one passed in, so the examples at the bottom read neatly.

Output:

six-node tree: [4, 2, 5, 1, 3, 6]
left chain:    [1, 2, 3, 4, 5]
empty tree:    []

Trace the loop on the six-node tree. cur starts at 1. The inner loop pushes 1, then 2, then 4, and then cur becomes None because 4 has no left child. The stack now holds [1, 2, 4] with 4 on the right end. Pop 4, add it to the output, and move to its right child, which is also None. The outer loop checks again: cur is None, but the stack is not empty, so the loop continues. Pop 2, add it, and move to 5. The inner loop pushes 5, finds no left child, and pops 5 straight away. The stack holds [1], so pop 1, add it, and move to 3. Pushing 3 and then popping it gives 3 before its child 6, and then the walk ends. The output list is [4, 2, 5, 1, 3, 6], the same as the recursive version.

The chain example shows why the iterative form matters. The chain has five nodes and does not need much stack space. A chain of a hundred thousand nodes would fail in the recursive version, but the iterative version only needs a list that holds one reference per node, which Python can store without trouble.

The recursion limit

Python has a setting for the deepest chain of recursive calls it allows. You can read it with sys.getrecursionlimit(). The check below builds a chain of 5,000 nodes and runs the recursive inorder function on it. The iterative version runs on the same chain without trouble.

Output:

recursion limit: 1000
iterative length: 5000
recursive version failed: maximum recursion depth exceeded

The limit is 1000 by default in this Python version, and the recursive call fails with a RecursionError once it goes deeper than that. The message is short, but the cause is the depth of the tree, not the number of nodes in some other sense. You can raise the limit with sys.setrecursionlimit, but a higher limit only moves the problem. A very deep tree still needs a very deep call stack, and the iterative version avoids that cost.

What it costs

Each node is pushed or visited exactly once in every version of the walk. The recursive version calls a function once per node and once per missing child. The iterative version pushes each node once and pops it once. Both take time proportional to the number of nodes. We write that as O(n), read as "order n", which means the time grows in line with n.

The space question is about the extra memory the walk needs at its peak. In the recursive version, the call stack holds one frame for each node on the path from the root to the current node. In the iterative version, the explicit stack holds the same nodes. That path is the height of the tree, written h. For a tree shaped like a balanced pyramid, h is about log of n, which is small. For a chain, h is n, which is as large as the tree itself. So the space is O(h), which lies between O(log n) and O(n) depending on the shape.

This is why the shape of a tree matters as much as its size. Two trees with the same number of nodes can behave very differently. In a balanced tree, a walk stays shallow. In a chain, it goes all the way down before it can come back.

Common mistakes and the errors they cause

Most bugs in the first tree programs you write fall into a few groups. Learn to recognise them, because the errors look frightening until you know what they mean.

Forgetting the None check

If you leave out the None check at the top of a traversal, the first call on a leaf's missing child crashes the program. Here is a version of inorder with no check, run on a tree with a single left child. The code is shown without the run mark because it stops with an error.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def inorder(node, out):
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
 
root = TreeNode(1)
root.left = TreeNode(2)
out = []
inorder(root, out)

The output is:

Traceback (most recent call last):
  File "main.py", line 17, in <module>
    inorder(root, out)
    ~~~~~~~^^^^^^^^^^^
  File "main.py", line 9, in inorder
    inorder(node.left, out)
    ~~~~~~~^^^^^^^^^^^^^^^
  File "main.py", line 9, in inorder
    inorder(node.left, out)
    ~~~~~~~^^^^^^^^^^^^^^^
  File "main.py", line 9, in inorder
    inorder(node.left, out)
            ^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'left'

Read the last line first. It names the type of error, AttributeError, and says what went wrong: a NoneType object, which is the Python name for None, has no attribute called left. The lines above it show the calls that led to the crash, with the oldest call at the top. The call on node 2 starts, then calls itself with its left child, None. That call's first line tries to read None.left, and it fails. The fix is to add if node is None: return at the top of the function.

Stack overflow from a missing base case

If the function never stops, Python keeps adding frames until it reaches the recursion limit, and then it raises RecursionError. A common typo causes this. Suppose the code passes the current node again instead of its left child, so preorder(node, out) where preorder(node.left, out) was meant. The call never gets smaller, so it never reaches None. Here is the output from a run of that bug. The code is shown without the run mark because it stops with an error.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def preorder(node, out):
    if node is None:
        return
    out.append(node.val)
    preorder(node, out)
    preorder(node.right, out)
 
 
root = TreeNode(1)
preorder(root, [])

The output is:

Traceback (most recent call last):
  File "main.py", line 17, in <module>
    preorder(root, [])
    ~~~~~~~~^^^^^^^^^^
  File "main.py", line 12, in preorder
    preorder(node, out)
    ~~~~~~~~^^^^^^^^^^^
  File "main.py", line 12, in preorder
    preorder(node, out)
    ~~~~~~~~^^^^^^^^^^^
  File "main.py", line 12, in preorder
    preorder(node, out)
    ~~~~~~~~^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The repeated lines show a function calling itself with the same node. Line 12 is the bad call, which passes node again. The [Previous line repeated 996 more times] line means the same frame appeared many more times before Python stopped it. The number depends on the Python version and on how much of the stack the program already used, so your count may differ. The fix is to pass the child, node.left, and not the node. Each recursive call must move closer to the leaves, so that it reaches None in the end.

Calling a method without self

Inside a class, every method's first parameter is self. If you write a method and forget it, Python reports a count mismatch when you call it.

class Walker:
    def preorder(node, out):
        if node is None:
            return
        out.append(node.val)
 
 
w = Walker()
w.preorder(None, [])

The output is:

Traceback (most recent call last):
  File "main.py", line 9, in <module>
    w.preorder(None, [])
    ~~~~~~~~~~^^^^^^^^^^
TypeError: Walker.preorder() takes 2 positional arguments but 3 were given

The message says the method takes two arguments, but three were given. Python passes the object itself as the first argument, so w.preorder(None, []) becomes Walker.preorder(w, None, []). The fix is to add self as the first parameter, or, as this lesson does, to write the traversals as plain functions outside a class.

Using a name that does not exist

If you misspell a function name or call it before it is defined, Python raises NameError.

def preorder(node, out):
    if node is None:
        return
    out.append(node.val)
 
 
print(preorde(None, []))

The output is:

Traceback (most recent call last):
  File "main.py", line 7, in <module>
    print(preorde(None, []))
          ^^^^^^^
NameError: name 'preorde' is not defined. Did you mean: 'preorder'?

Python points at the name and suggests the closest spelling it knows. Read the name in the message, check that the function exists with that exact spelling in the same file, and make sure it is defined above the line that calls it. Inside a single script, a function defined below the call does not exist yet when the call runs.

Mixing up the orders

It is easy to swap the order of the two recursive calls in preorder or to move the append line to the wrong place. Test every traversal on the six-node tree and check the output against the table in this lesson. If one output is wrong, find the line where the value is added and compare it with the visit sequence in the table.

Trailing spaces when printing a list of values

If you print each value with print(node.val, end=" ") in a loop, the line ends with a space. Most judges ignore trailing spaces, but a test that compares the exact text may not. Printing one list, as this lesson does, avoids the problem. When you want the values on one line without brackets, use print(*values), which passes each value as a separate argument and puts one space between them.

Debugging walkthrough: a tree that prints the wrong order

Suppose you write inorder and get [4, 2, 5, 1, 6, 3] for the six-node tree. The last two values are swapped. Start by asking which subtree produces that pair. Node 3 has only a right child, so the walk over 3 and 6 happens after node 1 is visited. If 6 comes before 3, the append for 3 runs after the call on its right child, so that line sits too low in the function.

Add a temporary print that shows the call and the current node. For example, put print("visit", node.val) in the function just before the append line. Run the program and read the trace from top to bottom. The line where 3 is printed will show whether it came before or after 6. Once you see the wrong order, look at the lines of the function that run in that order and move the append to the right place.

Remove the debug print before you submit. Leaving prints in a traversal changes the output and makes judges fail even when the logic is correct.

A tree from a list of values

Hand-built trees are fine for a small example, but a program often needs to read a tree from input. The module assignment and the practice problems use one common encoding, which you can read easily once you know it. It works like a grid of positions filled from the top row down, left to right.

The input gives a number n first. That number is how many items follow. The items come next, separated by spaces or line breaks. The item at position 0 is the root. The next two items are the left and right children of the root. The item after those is the left child of the first child, and so on, row by row. The word null marks a missing node, and missing nodes still take a position, because they keep the row order correct. The list stops after the last real node, so you do not write trailing null values.

For example, the input 7 and 1 2 3 4 5 null 6 describes the six-node tree. Position 0 is 1, the root. Positions 1 and 2 are the children 2 and 3. Positions 3 and 4 are the children of 2, which are 4 and 5. Position 5 is null, the missing left child of 3. Position 6 is 6, the right child of 3.

The program below reads that format from standard input and prints the preorder list. Standard input is the text your program receives from the keyboard, or from a file or a pipe. The builder uses a deque, a double-ended queue from the collections module. You will study queues properly in the third lesson. For now, you only need to know that a queue lets you attach children to nodes in the same order the values appear in the list.

import sys
from collections import deque
 
 
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def build(tokens):
    if not tokens or tokens[0] == "null":
        return None
    root = TreeNode(int(tokens[0]))
    pending = deque([root])
    idx = 1
    while pending and idx < len(tokens):
        parent = pending.popleft()
        if idx < len(tokens) and tokens[idx] != "null":
            parent.left = TreeNode(int(tokens[idx]))
            pending.append(parent.left)
        idx += 1
        if idx < len(tokens) and tokens[idx] != "null":
            parent.right = TreeNode(int(tokens[idx]))
            pending.append(parent.right)
        idx += 1
    return root
 
 
def preorder(node, out):
    if node is None:
        return
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)
 
 
data = sys.stdin.read().split()
n = int(data[0])
tokens = data[1:1 + n]
root = build(tokens)
pre = []
preorder(root, pre)
print(pre)

To run it, give the program this input, with the two lines typed as they are:

7
1 2 3 4 5 null 6

The output is:

[1, 2, 4, 5, 3, 6]

The build function takes one token at a time. idx points at the next token to read. Each node taken from the queue consumes two tokens, one for its left child and one for its right child. A null token consumes its position but adds no node. Because a null child is never added to the queue, no missing node ever gets a child of its own, which is the rule that keeps the list correct.

Notice what happens when the list ends early. The loop stops when either the queue is empty or no tokens are left, so any child whose position was never listed stays None. That is why the encoding does not need trailing null values.

The program reads all of standard input with sys.stdin.read() and splits it on any whitespace with .split(). That means the values can be on one line or several, just as in the format above. Each token is still text, so int(tokens[0]) converts the first one to a number before it goes into a node.

Counting nodes and leaves

Here is a last example of a complete recursive function. It counts every node and every leaf. Both counts follow the same pattern: a base case for None, then a result built from the two children.

Output:

nodes: 6
leaves: 3
leaves of a single node: 1

The leaf check is the subtle part. A None child is not a leaf. A leaf is a real node with two None children. That is why count_leaves returns 0 for None and 1 only when both children are missing. Adding one to count_leaves(node.left) for a None child would count nothing, which is the point of the base case.

Trace the count

Trace count_nodes on the three-node tree with root 1 and children 2 and 3. The call count_nodes(1) asks for count_nodes(2) and count_nodes(3). The call on 2 asks for two None values, each returns 0, so 2 returns 1 + 0 + 0, which is 1. The call on 3 also returns 1. Back at 1, the result is 1 + 1 + 1, which is 3. The answer climbs from the leaves to the root, and each node adds its own 1.

Variations and edge cases

The same pattern solves many questions. Here are a few variations to try in your head before you move on.

• Empty tree. The root is None. Every function should return its base-case answer. count_nodes(None) is 0, and inorder_iterative(None) returns an empty list. Test the empty tree in every function you write.
• Single node. The root has no children. It is also a leaf, so count_leaves returns 1. Its preorder, inorder and postorder are all the one value.
• Chain. Every node has one child. Inorder on a left chain prints the values from the bottom up, as the chain example showed, while preorder prints them from the top down.
• Perfect tree. Every level is full. A perfect tree of height h has 2 ** h - 1 nodes. The six-node tree is not perfect, because the level 2 slots are not all full. A tree of height 3 with seven nodes is perfect.
• Duplicate values. Nothing in a plain binary tree says values must be unique. The traversals still print each node once, even when two nodes hold the same number. Searching for a value in a tree with duplicates needs care, which the LCA lesson returns to.

Interview questions you should be able to answer

Interviewers ask traversal questions in a few standard forms. Here are the ones this lesson prepares you for, with a short answer to each.

What is the difference between preorder and postorder? Preorder visits a node before its children. Postorder visits it after both children. The same tree gives different lists, and the order decides which answers are ready when you need them.

Write inorder without recursion. Use the stack loop shown in this lesson. Push left as far as you can, pop, visit, then go right. The time is O(n) and the space is O(h).

Which traversal would you use to copy a tree? Preorder, because the parent is created first and then its children are attached to it. Postorder works too if you build the copy from the bottom up, but preorder matches the shape of the code more naturally.

What is the space complexity of a recursive traversal? O(h), where h is the height. Recursion uses one frame per level of the path, not per node. A balanced tree uses little space, and a chain uses as much as the number of nodes.

Why is each node visited exactly once? Each node is reached from its parent by one call. A tree has one path from the root to each node, so no node can be reached twice.

Real-world uses

Once you can walk a tree, you can recognise the patterns in many programs. A file explorer is a preorder walk: it shows a folder, then the files and folders inside it. A postorder walk computes the total size of a folder, because each folder needs the sizes of its children before it can report its own. A web browser builds a tree of the HTML elements on a page and walks it to apply styles and layout. A compiler parses code into a tree of operations, then walks the tree in postorder to produce instructions, because each operation needs its operands first. An expression such as (2 + 3) * 4 becomes a small tree with * at the root and + as its left child, and the postorder walk gives 2 3 + 4 *, the order a simple calculator needs.

These uses all rely on the same three ideas from this lesson: a None base case, a visit at a chosen point, and a recursive call for each child.

Practice

Try each exercise on paper first, then in code. Open the answer only after you have tried the exercise.

1. Draw the tree you get from the input 5 and 1 null 2 3 4. Then write its preorder by hand. Check your answer by running the builder program from this lesson with the same input.

Show the answer

The input puts 1 at the root with no left child. The root's right child is 2. Node 2 takes the next two positions, which are 3 and 4, as its left and right children. The preorder is [1, 2, 3, 4]. The null in position 1 is the root's missing left child, and it uses up one token but adds no node.

2. Write def size(node): that returns the number of nodes. It should match count_nodes from this lesson on any tree. Test it on an empty tree and a single node.

Show the answer

def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

This is the same as count_nodes. The base case returns 0 for None, and each real node adds 1 plus the sizes of its two subtrees. On an empty tree it returns 0, and on a single node it returns 1.

3. Write def postorder(node, out): and check its output on the six-node tree. Then change the tree by adding a node with value 7 as the left child of 4, and predict the new postorder before you run the code.

Show the answer

Adding 7 as the left child of 4 makes the postorder [7, 4, 5, 2, 6, 3, 1]. Postorder visits the left subtree, then the right subtree, then the node. The subtree under 2 starts with 4's subtree, which is 7 then 4. Next comes 2's right child 5, then 2 itself. Trace it by writing the call order on paper before you run the code.

4. Write def reverse_preorder(node, out): that visits the right child before the left child. Predict the output on the six-node tree before you run it.

Show the answer

def reverse_preorder(node, out):
    if node is None:
        return
    out.append(node.val)
    reverse_preorder(node.right, out)
    reverse_preorder(node.left, out)

On the six-node tree the output is [1, 3, 6, 2, 5, 4]. The function is still preorder, with the node first, but the subtrees are visited in the other order.

5. Write def count_one_child(node): that counts the nodes with exactly one child. Test it on the six-node tree (answer: 1) and on the chain of five nodes (answer: 4).

Show the answer

def count_one_child(node):
    if node is None:
        return 0
    here = 0
    if (node.left is None) != (node.right is None):
        here = 1
    return here + count_one_child(node.left) + count_one_child(node.right)

The test (node.left is None) != (node.right is None) is true when exactly one of the two children is missing. On the six-node tree the answer is 1, because only node 3 has exactly one child: its right child 6. Nodes 1 and 2 have two children, and the leaves have none. On the chain of five nodes the answer is 4, because each of the top four nodes has exactly one child.

6. Write def leaves_left_to_right(node, out): that adds the leaves to out in left-to-right order. Predict the answer for the six-node tree: it should be [4, 5, 6].

Show the answer

def leaves_left_to_right(node, out):
    if node is None:
        return
    if node.left is None and node.right is None:
        out.append(node.val)
        return
    leaves_left_to_right(node.left, out)
    leaves_left_to_right(node.right, out)

The walk visits the children in left-then-right order, so the leaves come out left to right. On the six-node tree the output is [4, 5, 6].

7. Use the iterative inorder function to return the values of a tree with a single node. Explain in one sentence why the outer loop ends after one pass.

Show the answer

For a tree with a single node, the outer loop runs once. The inner loop pushes the root, finds its left child None, and stops. The function pops the root, appends it, then moves to the right child, which is None. The outer loop checks again: cur is None and the stack is empty, so the condition cur is not None or stack is false, and the loop ends.

8. Explain in your own words why preorder and inorder together are enough to rebuild a tree with distinct values, while preorder alone is not.

Show the answer

Preorder tells you which value is the root, because the first value is always the root. Inorder tells you which values lie to the left of the root and which lie to the right. Together they split the tree into two halves at each level. Preorder alone cannot tell you where the left subtree ends and the right one begins, so many different trees share the same preorder list.

9. Change inorder_iterative so that it returns the values in reverse order without changing the loop. Hint: think about the last thing the function does before it returns.

Show the answer

Reverse the list just before the return: out.reverse() changes the list in place, and return out[::-1] returns a reversed copy. Both give [6, 3, 1, 5, 2, 4] on the six-node tree. The slice [::-1] is the step-by-minus-one slice, which reads a sequence backwards.

10. Write a function that returns True when two trees have the same preorder list and False otherwise. Test it with two trees that differ only by a missing child.

Show the answer

def same_preorder(a, b):
    pa = []
    pb = []
    preorder(a, pa)
    preorder(b, pb)
    return pa == pb

The helper preorder is the one from this lesson. Two trees with a missing child in different places can still produce the same preorder if the values happen to match in order. For example, a root with only a left child and a root with only a right child both give [1, 2]. This test is weaker than comparing the whole shape. The shape check is a separate problem.

11. Add a max_depth(node) function that returns the largest depth of any node, where the root has depth 1. Compare your answer with the height rules in the next lesson before you move on.

Show the answer

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

This returns 3 for the six-node tree, because the deepest leaves 4, 5 and 6 sit three nodes deep when the root counts as 1. The next lesson explains why the same function gives the height of a tree.

12. Write a program that builds the tree from its input, then prints the number of nodes at each depth. Use the input 7 and 1 2 3 4 5 null 6. Expected output: 1 node at depth 0, 2 nodes at depth 1, and 3 nodes at depth 2, one line per depth.

Show the answer

Use the level-by-level idea from the third lesson, or a recursive walk that passes the depth down. A recursive version passes depth + 1 to each child and adds one to a list indexed by depth. Print one line per depth, with the count and the word "node" or "nodes". Check that the total of all counts is 6.

What you now know

• A tree is a set of nodes where each node except the root has exactly one parent. A binary tree allows at most two children, called left and right.
• A missing child is None. Every tree function starts with a None check, which is the base case of the recursion.
• Preorder visits the node before its children, inorder visits it between them, and postorder visits it after them.
• The recursive and iterative traversals visit each node once, so they take O(n) time. Their space is O(h), the height of the tree.
• The stack in the iterative version lets you walk deep trees without hitting Python's recursion limit.
• The list encoding with null gives you a simple way to build trees from input, and the module assignment uses it.