Binary tree terminology and structure

Why it matters

Trees show up wherever things nest inside other things. Folders hold files and other folders. A company chart shows who reports to whom. A web page is stored as a tree of elements, and an arithmetic expression such as (2 + 3) * 4 is a tree too. A binary tree is the simplest kind, with at most two children per node, and it is the base for search trees, heaps, expression parsers and many interview questions.

Every tree problem starts with the same words and the same picture. If you do not know the words, the solutions in the next lessons will look like magic. So this lesson gives you the vocabulary, the C++ structure that stores a tree, and four complete programs you can run in this page.

The idea

Start with something you already use. Your computer keeps files in folders. A folder can contain files and other folders, and each of those can contain more. If you draw it on paper, you start with one box at the top and draw lines down to the boxes inside it. Each of those boxes has its own lines going down. Nothing joins back together, and every box has exactly one box above it, except the top one. That drawing is a tree.

In computer science, a tree is a set of nodes joined by edges. A node is a box that holds one value. An edge is the line between a box and the box directly below it. A tree follows two rules:

1. One node is at the top. It is called the root.
2. Every other node has exactly one parent directly above it.

Because of these rules, there is exactly one path between any two nodes. You never have two different routes from one box to another box.

A binary tree adds one more rule: every node has at most two children, and the two children are called left and right. The word "binary" means two. It says nothing about the values stored in the nodes. The node holding 1 can have a child holding 9 and a child holding 2, and the tree is still a binary tree. A later module adds an ordering rule, which gives a binary search tree. Here, the values can be in any order.

Here is a binary tree with six nodes:

A binary tree with six nodes. The root is 1, its children are 2 and 3, and the leaves are 4, 5 and 6

The same tree in plain text, which is useful when you sketch on paper:

        1          <- root
       / \
      2   3        <- 2 and 3 are children of 1
     / \   \
    4   5   6      <- 4, 5, 6 are leaves

Read the tree from the top. The root is 1. Its left child is 2, and its right child is 3. Node 2 has two children, 4 and 5. Node 3 has no left child and one right child, 6. Nodes 4, 5 and 6 have no children at all, so they are leaves.

Vocabulary

Interviewers use these words without explaining them, so learn them now. The table uses the tree above.

The depth looks up from a node, toward the root. The height looks down, toward the leaves. For the root, the depth is 0. For a leaf, the height is 0. Beginners mix these two up most often, so when you see the words, ask yourself which direction the measurement goes.

Edges or nodes: check the convention

The table counts edges. An edge is the line between a parent and a child, so the path 1, 2, 4 has two edges. Many textbooks and some interview problems count nodes instead. Under that rule, the path 1, 2, 4 has three nodes, and a tree with only one node has height 1, not 0.

The two rules differ by exactly one, and that difference causes off-by-one bugs. Before you write any code for a height question, read the problem and decide which convention it uses. In the next lessons, the code shows the convention in a comment, and you should always check for one.

Special shapes

Binary trees come in a few named shapes. Each shape has a rule that you can test in code.

• Full: every node has either zero children or two children. The root in the example above is not full, because node 3 has only one child.
• Complete: every level is completely filled, except possibly the last one, and the last level fills from the left. Heaps use this shape, because it lets you store the tree in an array with no gaps.
• Perfect: every leaf is at the same depth, and every node that is not a leaf has exactly two children. A perfect tree with height h has 2 to the power (h + 1) minus 1 nodes.
• Skewed: every node has at most one child, and all the children point the same way. A skewed tree behaves like a linked list. Its height equals the number of nodes minus one.

Work out the perfect-tree formula once, because it appears in complexity questions. A perfect tree with three levels below the root, numbered 0 to 3, has 1 node at depth 0, 2 at depth 1, 4 at depth 2 and 8 at depth 3. The total is 1 + 2 + 4 + 8, which is 15. That is 2 to the power 4 minus 1, and the height of that tree is 3, so the formula gives 2 to the power (3 + 1) minus 1, which is also 15.

Skewed trees matter because they are the worst case. If a tree of n nodes is skewed, then a recursive function that walks it goes n calls deep. If the tree is perfect, the same walk goes only about log n calls deep. You will see this difference again when we talk about complexity.

What a node is in C++

A program needs a way to store a tree in memory. In C++ you use a struct, which groups several fields under one name. A tree node has three fields: the value, a pointer to the left child, and a pointer to the right child.

A pointer is a variable that stores the memory address of something else. The type TreeNode* means "the address of a TreeNode". An address is like a house number. Holding the address lets you visit the house, but the address itself is not the house.

Here is the struct and a constructor, which is the piece of code that sets up a new node:

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

Read the constructor from the inside out. TreeNode(int v) says that you create a node with one number. The part after the colon sets val to v, sets left to nullptr, and sets right to nullptr. The word nullptr means "a pointer that points to nothing". A missing child is represented by nullptr. A missing root, which means an empty tree, is also nullptr.

Each new TreeNode(...) call asks the computer for a fresh block of memory, big enough for one node, and returns the address of that block. On a 64-bit machine, a node built from this struct takes 24 bytes: 4 bytes for the int, 4 bytes of padding so the pointers line up, and 8 bytes for each pointer. The exact size depends on your machine, but 24 is typical.

The arrow operator -> reads a field through a pointer. If root is a TreeNode*, then root->val means "go to the node that root points to, then read its val field". The expression root->left->right means "go to the node root points to, go to its left child, then go to that child's right child". Each arrow follows one edge.

A node in memory as three boxes: the value, the left pointer and the right pointer. The left pointer has an arrow to node 2, and missing children hold null

The picture shows what the struct looks like in memory. Each node is a separate block that holds a value and two arrows. The arrows are pointers. A node does not know its parent, unless you add a parent field yourself. That is why a tree is often walked from the top down, starting at the root.

Worked example 1: build a tree by hand

The first program builds the six-node tree from the picture, one node at a time. Leave the Input box empty and click Run.

1
5
1

Trace the first three lines of main. The first line creates a node holding 1 and stores its address in root. The second line creates a node holding 2 and stores its address in root->left. The third line does the same for 3 on the right. Lines four to six attach 4 and 5 below 2, and 6 below 3.

Now look at the three output lines. root->val is 1. The path root->left->right goes from the root to 2 and then to 5, so it prints 5. The last line asks whether root->right->left is nullptr. Node 3 has no left child, so the answer is true. C++ prints a true bool as 1, which is why the output shows 1 and not the word true.

Notice how much typing it takes to build a tree this way. Each node needs its own line, and you have to write the path to reach the parent. Later in this lesson you will read the same tree from input, which is much faster for testing.

Level-order input: the -1 convention

When a tree is written as a line of numbers, the usual convention is to list the nodes level by level, from left to right, and to write -1 for every missing child. This is called level order or breadth-first order. The tree from the picture is:

1 2 3 4 5 -1 6

Read the list with a finger. The first number, 1, is the root. The next two numbers, 2 and 3, are the children of the root. The next two, 4 and 5, are the children of 2. Then comes -1, which is the missing left child of 3. Then comes 6, which is the right child of 3.

Here is how the builder turns that list into nodes. It keeps a queue, which is a line where you add people at the back and serve them from the front. A queue holds the nodes that are waiting for their children to be filled in. Each step takes one node off the front, reads the next two numbers from the list, and gives that node its left and right children.

The builder stops when the list runs out. The nodes still in the queue, 4, 5 and 6, have no children, because the list has no numbers left for them. Those are the leaves.

The code for the builder is below. It is used in the next two programs, so read it carefully once.

TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < a.size()) {
        TreeNode* n = q.front();
        q.pop();
        if (i < a.size() && a[i] != -1) {
            n->left = new TreeNode(a[i]);
            q.push(n->left);
        }
        i++;
        if (i < a.size() && a[i] != -1) {
            n->right = new TreeNode(a[i]);
            q.push(n->right);
        }
        i++;
    }
    return root;
}

The function returns nullptr for an empty list or a list that starts with -1. Otherwise, it creates the root and then loops. The variable i is the position of the next number in the list. Each node taken from the queue uses two positions, one for its left child and one for its right child. A child is created only when its number is not -1, and only the real children go into the queue. The check i < a.size() protects you from reading past the end of the list, which would be undefined behaviour. Undefined behaviour means the program may do anything, including crash or print a wrong answer, so it is a bug even when the output looks fine.

Worked example 2: count nodes and leaves from input

The next program reads a level-order list from the Input box, builds the tree, and then counts its nodes and leaves. It uses the two recursive functions that you will meet in the next section, so do not worry about how they work yet. Just see what the program prints.

Type this into the Input box, on one line, and then click Run:

1 2 3 4 5 -1 6

6 nodes
3 leaves

The loop while (cin >> x) reads one integer at a time. It stops when there is nothing left to read. In the browser, the Input box provides that text, so the program sees the same numbers you typed. The values go into the vector values, which is C++'s resizable array. Then build turns the list into a tree, and the two counting functions walk the tree.

The count of nodes is 6, because the tree has six real values. The count of leaves is 3. Those are 4, 5 and 6. Node 2 is not a leaf, because it has children 4 and 5, and node 3 is not a leaf, because it has child 6.

If you type -1 in the Input box, the list is [-1], the builder returns nullptr, and the output becomes 0 nodes and 0 leaves. Try that once. An empty tree is a real case, and your functions must handle it.

The recursive template

Almost every tree function has the same shape. A tree is recursive, which means each child is the root of a smaller tree. The left child of a node is the root of its own left subtree, and that subtree has the same shape as the whole tree. So a function can solve the problem for a node by solving it for each child and then combining the answers.

Use this template for almost any tree question:

1. Base case: if the node is nullptr, return a simple answer. For counting, that answer is 0. For a yes-or-no question, it might be true.
2. Recurse: ask the left child and the right child for their answers.
3. Combine: add or compare the answers with the current node, and return the result.

Trace countNodes on the tree from the picture. The call countNodes(1) is not a base case, so it calls countNodes(2) and countNodes(3). The call countNodes(2) calls countNodes(4) and countNodes(5). Each of those calls the two children, which are nullptr. Those calls return 0 immediately. So countNodes(4) returns 1 + 0 + 0, which is 1. The same happens for 5. Then countNodes(2) returns 1 + 1 + 1, which is 3. The call countNodes(3) has a left child that is nullptr, so the left call returns 0, and the right call countNodes(6) returns 1. So countNodes(3) returns 1 + 0 + 1, which is 2. Finally countNodes(1) returns 1 + 3 + 2, which is 6.

The count of leaves works in a similar way, but the base case is different. A node with no children is a leaf and returns 1. A node with children adds the answers from its subtrees. The code checks !n->left && !n->right to see whether both children are null.

Here is the first mistake people make, and it is easy to see on paper. If you write the leaf check before the null check, you read n->left on a null pointer. That is a crash. Always put the if (!n) base case first.

Printing the tree sideways

A tree is easier to see when you turn it on its side and print it with indentation. The usual trick prints the right subtree first, then the node, then the left subtree. Because the right side comes first, it appears above the left side, which matches the picture you have been drawing.

Each level of depth adds four spaces. Here is the program. Type the same input as before, 1 2 3 4 5 -1 6, into the Input box.

        6
    3
1
        5
    2
        4

Read the output from the top, and imagine tilting your head to the left. The 6 is the right child of 3, so it is the highest and most indented line on the right side. The 3 sits one level in, and 1 is the root at the left edge. Then the left side appears below: 5 is the right child of 2, and 4 is the left child of 2.

Trace the first few calls to see the order. showSideways(1, 0) calls showSideways(3, 1) first. That calls showSideways(6, 2), which has no children, so it prints eight spaces (two levels of four) and then 6. Back in the call for 3, it prints four spaces and 3. Its left child is null, so the call ends. Back in the call for 1, it prints the root with no indentation. Then it handles the left side, and the same pattern produces the lines for 5, 2 and 4.

This program only prints. The recursion that visits every node once is the same pattern that the traversal lesson turns into a formal technique, so it is worth tracing once by hand.

Summing and finding the maximum

One more program shows that the template works for any combining rule. It sums all the values and finds the largest value. The base case for the sum is 0, and the base case for the maximum is a value smaller than every real node. Because the values here are positive, 0 works as the smallest value.

Type 1 2 3 4 5 -1 6 into the Input box again.

sum 21
max 6

The sum is 1 + 2 + 3 + 4 + 5 + 6, which is 21. The maximum is 6. Notice the shape of each function: the base case returns the neutral answer for nullptr, and the combining step adds or takes the maximum of the current value and the two child answers.

There is a subtle point about maxValue. It returns 0 for an empty subtree. If every real value in a tree were negative, that 0 would win the comparison and the answer would be wrong. This is a real bug category: a sentinel value that looks neutral but is not. Lesson 3 returns to the same idea when it computes the diameter. For now, remember that the base case of a combining function must be a true neutral value for the operation, or you must handle the empty tree in a separate check.

What the computer does inside

Each recursive call uses a block of memory on the call stack. A call stack is a stack of frames, one frame per active call. A frame holds the parameters (here, one pointer) and the place to return to. When a call returns, its frame is removed. A tree function that goes down the left side first and then the right side creates a chain of frames as deep as the tree is tall.

So the memory cost of a tree function has two parts. The nodes themselves take memory on the heap, which is the big pool of memory that new uses. The recursion takes memory on the call stack, one frame for each level it goes down. For a tree of n nodes and height h, the recursion uses about h frames, and the nodes use about n times 24 bytes on a 64-bit machine.

Notice that h is the important number for the stack. A perfect tree with a million nodes has a height of about 20, so the recursion is shallow. A skewed tree with a million nodes has a height of one million, which can overflow a typical call stack of a few megabytes. The stack overflow then looks like a crash, with no message about trees. Lesson 2 explains iterative traversals, which use a stack you control, for exactly this reason.

Complexity

Let us write the costs in the standard form. Let n be the number of nodes and h the height.

• Building the tree from the list takes O(n) time. Each number is read once and each node is created once.
• countNodes, countLeaves, sumValues and maxValue each take O(n) time, because every node is visited exactly once.
• Each of those functions uses O(h) extra space for the call stack. In the worst case, h equals n, so the space is O(n).
• The tree itself takes O(n) space on the heap.

A common interview question asks "how much memory does the recursion use?" The answer is the height of the tree, not the number of nodes. Knowing this, you can say that a balanced tree is cheaper to walk recursively than a skewed tree of the same size.

Edge cases you must test

An edge case is an input at the limit of what a problem allows. For trees, the common ones are these:

• Empty tree: the root is nullptr. The input -1 gives an empty tree in the convention above. Every function must return its neutral answer, and nothing should dereference the root.
• One node: the root has no children. It is a leaf and the root at the same time. Count it once.
• Skewed tree: every node has one child. Recursion goes as deep as the number of nodes. This is the worst case for stack space.
• Duplicate values: a plain binary tree does not forbid two nodes with the same value. Compare nodes by pointer when you need to say "the same node", and compare values only when the problem asks for values.
• Missing children in the middle: the list 1 -1 2 means 1 has no left child and a right child 2. Level order keeps the position of each child, even when the earlier child is missing.

Check at least the empty tree and the one-node tree in every function you write. Most bugs in tree code show up at these two sizes.

Common mistakes and their real messages

Each mistake below comes with the message you will see, so that you can recognise it fast. The messages come from g++ 15 on Linux. Other compilers word them slightly differently, but they mean the same thing.

Using a field name that does not exist

If you type root->valu for root->val, the compiler stops with this message:

error: 'struct TreeNode' has no member named 'valu'; did you mean 'val'?

The compiler even suggests the right name. Read the last word of the message. Here it names the field you probably meant.

Assigning a node instead of a pointer

If you write root->left = n; where n is a TreeNode (not a TreeNode*), the compiler reports:

error: cannot convert 'TreeNode' to 'TreeNode*' in assignment

The fix is to create the node with new, which returns a pointer, or to take its address with &n. The rule to remember is that a child field holds an address, so it needs a pointer.

Dereferencing a null child at run time

This is the most common bug, and it is not caught by the compiler. Here is a program that reads a child that does not exist:

#include <iostream>
using namespace std;
 
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};
 
int main() {
    Node* root = new Node(1);
    cout << root->left->val << "\n";
    return 0;
}

The program compiles without errors. It crashes when it runs. A Linux shell reports exit status 139, which means the program received a segmentation fault. A segmentation fault is the operating system stopping a program that touched memory it does not own. Reading from address 0, which is what nullptr is, is one such touch.

When you compile the same program with AddressSanitizer, a tool that checks memory accesses while the program runs, you get the exact line:

ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000
The signal is caused by a READ memory access.
Hint: address points to the zero page.
    #0 ... in main your-file.cpp:13

The line number 13 in that message points at the cout line that reads root->left->val. To build the sanitizer version, add -g -fsanitize=address to the g++ command. The -g flag keeps line numbers, and the sanitizer checks memory. The program still crashes, but now you know where.

Forgetting the base case

If a counting function has no if (!n) return 0; check, the recursion calls itself on a null child and then reads n->left on that null pointer. You get the same segmentation fault. A different form of the same bug is a missing return in the base case, which causes the recursion to run forever. An endless recursion ends with a stack overflow, and the program is killed with the same exit status 139.

Debugging walkthrough

Suppose countNodes crashes on a tree that came from the input box. Here is a method that works without any special tools, which matters because a plain Linux system often has no debugger installed.

First, reproduce the crash with the smallest input that fails. Start with -1 (empty tree), then 1 (one node), then 1 2 (one child). If the one-node case passes and 1 2 fails, the bug is in the code for a missing right child.

Second, print the state at the line you suspect. Add a line such as cout << "visiting " << (n ? n->val : -1) << "\n"; at the top of the function. The ? : operator is a short if-else that gives n->val when n is not null, and -1 when it is null. The output shows you the order of the calls. The last line printed before the crash is the node whose child you read incorrectly.

Third, compile with the sanitizer, as shown above. The sanitizer names the line and the kind of bad memory access. Do this once for each crash, and you will learn the messages quickly.

Fourth, after you fix the bug, go back to the smallest failing input and check that it now prints the right answer. Then test the empty tree and the skewed tree again. A fix that handles one case often breaks another.

Interview questions you should be ready for

Interviewers use the vocabulary of this lesson as a quick test. These are the questions you will hear, with short answers:

• What is the difference between a tree and a binary tree? A tree can have any number of children per node. A binary tree allows at most two, called left and right.
• How many edges does a tree with n nodes have? n minus 1. Every node except the root has exactly one parent edge going up.
• What is the height of an empty tree? It depends on the convention. Counting edges, it is -1 or undefined. Counting nodes, it is 0. Always state which one you use.
• How many nodes does a perfect tree of height h have? 2 to the power (h + 1) minus 1, as shown earlier.
• Why is a recursive walk over a skewed tree a problem? Its height equals n, so the call stack holds n frames, and a large n can overflow the stack.

Real-world uses

Trees are everywhere in software, and you have probably used several without knowing it. A file explorer draws a tree of folders. A compiler reads source code into a tree called a syntax tree, and it checks the tree to decide whether the program is valid. A calculator evaluates 2 + 3 * 4 by building a tree in which * sits below +, so the multiplication happens first. A web browser builds the DOM, a tree of elements, from the HTML text. A decision tree in machine learning asks questions at each node and reaches a prediction at a leaf. In every case, the tree is the shape that hides the details and keeps the nesting.

Practice

Try each exercise on paper first, then in the box. The solutions are hidden. Open one only after you have written your own answer, or you have tried for at least ten minutes.

1. Draw a perfect tree with height 2, which has levels 0 to 2. Count its nodes and check the answer against the formula 2 to the power (h + 1) minus 1.

2. Write int countOneChild(TreeNode* n) that returns the number of nodes that have exactly one child. Use the recursive template.

int countOneChild(TreeNode* n) {
    if (!n) return 0;
    int here = ((n->left != nullptr) != (n->right != nullptr)) ? 1 : 0;
    return here + countOneChild(n->left) + countOneChild(n->right);
}

3. Write bool isFull(TreeNode* n) that returns true when every node has zero or two children. Treat the empty tree as full.

bool isFull(TreeNode* n) {
    if (!n) return true;
    if ((n->left == nullptr) != (n->right == nullptr)) return false;
    return isFull(n->left) && isFull(n->right);
}

4. Predict the output of the sideways program when the Input box holds 1 -1 2 -1 3. Then run it to check.

        3
    2
1

5. Write int countInner(TreeNode* n) that counts nodes with at least one child. For the example tree, the answer is 3, because nodes 1, 2 and 3 are inner.

int countInner(TreeNode* n) {
    if (!n) return 0;
    if (!n->left && !n->right) return 0;
    return 1 + countInner(n->left) + countInner(n->right);
}

6. Write int countAtDepth(TreeNode* n, int d) that returns the number of nodes at depth d, where the root has depth 0. For the example tree, depth 2 holds 4, 5 and 6, so the answer is 3.

int countAtDepth(TreeNode* n, int d) {
    if (!n) return 0;
    if (d == 0) return 1;
    return countAtDepth(n->left, d - 1) + countAtDepth(n->right, d - 1);
}

7. Explain in your own words why countLeaves(nullptr) returns 0 and does not crash. Then explain why countLeaves would crash if the check if (!n) return 0; were removed.

8. Find the bug. The function below should return the number of nodes, but it crashes on every tree.

int countNodes(TreeNode* n) {
    return 1 + countNodes(n->left) + countNodes(n->right);
}

9. A learner writes root.left->val in main, where root is declared as TreeNode* root. Explain the error, and write the correct expression.

10. A tree has n nodes. How many edges does it have? Explain with the picture from this lesson, and then say why the answer does not depend on the shape.

What you now know

• A binary tree is a set of nodes, each with a value and at most two children, left and right.
• Depth counts down from the root, and height counts up from the leaves. Always check whether the problem counts edges or nodes.
• Perfect, complete, full and skewed trees are the named shapes, and a perfect tree of height h has 2 to the power (h + 1) minus 1 nodes.
• In C++, a node is a struct with a value and two TreeNode* pointers, and nullptr marks a missing child.
• The -1 convention in level order turns a line of numbers into a tree, with a queue to track the nodes that still need children.
• Every tree function follows the template: base case, recurse on both children, combine the answers.
• The recursion uses O(h) stack space, and a skewed tree has the worst height.
• The most common bug is dereferencing a null child, which gives exit status 139. The sanitizer build shows the line.