Extended Binary Trees Explained Simply: Why We Add "Empty Seats" to a Tree and Where They Help

Describe the picture

Let me ask you something strange.

Why would anyone take a perfectly good tree and add extra nodes to it on purpose?

It sounds like making your homework longer for no reason. But in the world of data structures, this little trick is surprisingly useful. It makes some problems much easier to think about, and it sits quietly behind things you use every day, like file compression.

By the end of this article you will know:

what an extended binary tree is,
how to turn any ordinary binary tree into one,
why we do it, and
where it is actually useful.

No heavy maths, I promise. If you know what a binary tree looks like, you are ready. And if you don't, the next section has you covered.

First, a Quick Warm-up (Skip It if You Know Binary Trees)

A binary tree is like a family tree where every person can have at most two children: a left child and a right child.

A few words we will keep using:

Node: one box in the tree (one person in the family tree).
Child: a node hanging directly below another node.
Root: the node at the very top.
Leaf: a node with no children at all.
NULL (or "nothing"): what a computer stores when a child does not exist.

Here is a small binary tree:

      A
     / \
    B   C

A has two children (B and C). B and C have none, so they are leaves.

Now look closely at that picture. Where are the missing children of B and C? They are not drawn. In the computer they are just NULL. The tree is quietly hiding its empty spots.

And that is exactly what an extended binary tree fixes.

What Is an Extended Binary Tree?

An extended binary tree is an ordinary binary tree where we fill every empty spot with a special extra node.

Think of a cinema. A normal tree only describes the people who came. An extended tree also draws the empty seats, so that every row is completely filled, either with a person or with an empty-seat marker.

Let's do it with our tree. Every empty child spot gets a small square [ ]:

          (A)
         /   \
       (B)   (C)
       / \   / \
     [ ] [ ] [ ] [ ]

We now have two kinds of nodes, and they have official names:

Kind	Looks like	Also called	What it is
Internal node	circle `( )`	the real nodes	the nodes that were in the original tree
External node	square `[ ]`	the fake nodes, placeholders	the empty spots we added

Notice the new rule that appears all by itself:

In an extended binary tree, every node has either 0 children or exactly 2 children. Never just one.

Internal nodes always have two children (a real one or a square). Squares have none. That neat, tidy rule is the whole reason this tree is useful. (Because of this rule, you will also hear it called a 2-tree.)

A tiny warning about the word "leaf"

This confuses almost every beginner, so let's clear it up now.

In the ordinary tree, B and C were leaves.
In the extended tree, B and C are internal nodes, because they now have children (the squares).
The only leaves of the extended tree are the squares.

So after extending, the leaves are always the external nodes. Remember that, and half the confusion disappears.

How to Build One in 3 Easy Steps

Take any binary tree and do this:

Look at every node in the tree.
If a node is missing its left child, hang a square there.
If a node is missing its right child, hang a square there.

That's it. You do not need to change or move a single original node.

Let's try a skinny tree, a chain where each node only has a left child:

  A
 /
B
/
C

Which spots are empty?

A is missing its right child → 1 square.
B is missing its right child → 1 square.
C is missing both children → 2 squares.

Total: 4 squares.

              (A)
             /   \
          (B)     [ ]
         /   \
      (C)     [ ]
      /  \
    [ ]  [ ]

Now compare with the first example. It had 3 real nodes and 4 squares. This one also has 3 real nodes and 4 squares. Coincidence?

The Neat Pattern: Squares = Circles + 1

Count them up in both examples:

Tree	Real nodes (circles)	Empty spots (squares)
Example 1	3	4
Example 2	3	4

In every extended binary tree:

Number of external nodes = Number of internal nodes + 1

Or in short: E = I + 1.

Why is this always true? (A friendly proof)

Think about the lines (edges) in the tree.

Every circle has exactly 2 lines going down. So if there are I circles, there are 2 × I lines.
But in any tree, the number of lines is always one less than the number of nodes (every node except the root has exactly one line coming into it from above). The total number of nodes is I + E, so the lines are I + E − 1.

Both counts describe the same lines, so:

2 × I  =  I + E − 1
    I  =  E − 1
    E  =  I + 1

Done. A fact that is always true, with no exceptions.

A real-life way to feel this

Imagine a sorted shelf with 3 books on it. Where could a new book be placed?

before the first book,
between book 1 and book 2,
between book 2 and book 3,
after the last book.

That is 4 places. 3 books, 4 gaps. n books always make n + 1 gaps.

In the tree, the circles are the books and the squares are the gaps. Hold on to this picture. It is about to become very useful.

So... Why Do We Use Them?

Fair question. A tree with extra empty boxes sounds like waste. Here are the honest reasons.

Reason 1: "Nothing" becomes something you can count and talk about

In an ordinary tree, a missing child is just NULL, which means "nothing here". You cannot point at nothing, count it, or draw it.

In an extended tree, every empty spot is a real, visible node. That is a big deal for people who analyse algorithms, because suddenly every possible "dead end" has a name and can be counted.

Reason 2: The rule "0 or 2 children" makes everything cleaner

Compare these two sentences:

Ordinary tree: "A node can have 0, 1 or 2 children, and which child is missing matters."
Extended tree: "A node has 0 or 2 children."

Fewer cases means fewer bugs, shorter proofs, and simpler algorithms. When mathematicians and computer scientists can get rid of the "just one child" case, they happily do.

Reason 3: It gives us a clean formula to measure how "good" a tree is

Two numbers describe how deep the nodes sit in the tree:

Internal path length: add up the depth (steps from the root) of every circle.
External path length: add up the depth of every square.

For our first example (A on top, B and C below):

Depths of circles: A = 0, B = 1, C = 1 → internal path length = 2.
Depths of squares: all four are at depth 2 → external path length = 8.

And there is a beautiful rule connecting them (n is the number of circles):

External path length  =  Internal path length  +  2 × n
              8       =           2            +  2 × 3      ✔

You do not need to memorise this today. Just know that this clean relationship exists because we added the squares.

Where Are Extended Binary Trees Useful? (Four Real Places)

This is the part I enjoy the most, because it shows the idea is not just textbook theory.

1. Huffman coding: how files get compressed

Have you ever made a ZIP file or a JPEG? Compression is how big files become small ones, and one famous method is Huffman coding.

The idea is something you already do in real life. When you chat with friends, you shorten the words you use a lot: "lol", "brb", "omw". Rare words stay long. Common things get short names. Rare things get long names.

Huffman coding does this with letters. Let's say a message has these letters:

Letter	Times used
A	5
B	2
C	1
D	1

The computer builds a tree where the letters sit at the squares (external nodes) and the path to a letter is its secret code: left = 0, right = 1.

          (•)
         /   \
       A      (•)
      (0)    /   \
           B     (•)
          (10)   /  \
                C    D
              (110) (111)

So the codes are: A = 0, B = 10, C = 110, D = 111.

Count the bits for the whole message (9 letters):

Using fixed 2-bit codes for all four letters: 9 × 2 = 18 bits
Using Huffman codes: 5×1 + 2×2 + 1×3 + 1×3 = 15 bits

We saved space just by arranging the tree cleverly. On a big file, the saving is huge.

Why external nodes matter here: the letters sit only at the ends of the branches, never in the middle. That guarantees no code is the beginning of another code. (A = 0 is never the start of B = 10.) So when the computer reads a stream of 0s and 1s, it always knows exactly where one letter ends and the next begins. Without this, decoding would be a mess.

2. Searching: where does a failed search end?

Remember the bookshelf with n books and n + 1 gaps? Here is how that connects to a binary search tree.

Suppose a tree holds the numbers 10, 20, 30, and you search for 25:

Compare with 10: 25 is bigger, go right.
Compare with 20: 25 is bigger, go right.
Compare with 30: 25 is smaller, go left... and there is nothing there.

You have reached an empty spot, a square. That square means "25 is not in the tree."

Every unsuccessful search ends at exactly one square. And since a tree with n keys has n + 1 squares, there are exactly n + 1 different "not found" answers, one for each gap between your numbers.

Computer scientists use this to work out the average cost of searching, both for numbers that are in the tree (they end at circles) and for numbers that are not (they end at squares). Having the squares drawn makes that calculation clean.

3. Decision trees: why sorting can never be magically fast

Have you ever played 20 Questions? Someone thinks of an object and you ask yes/no questions until you guess it. Each question splits the possibilities into two groups.

That game is a tree:

every question is a circle (internal node) with two branches, yes and no,
every final answer is a square (external node).

Now apply that to sorting. Imagine sorting three numbers by comparing two at a time. Each comparison is a yes/no question, so a circle. The final sorted order is a square. For 3 numbers there are 3 × 2 × 1 = 6 possible orders, so the tree needs 6 squares.

A tree with 6 squares cannot be shorter than 3 levels (2 levels hold only 4 squares). So sorting 3 numbers by comparisons needs at least 3 comparisons in the worst case. No clever trick can beat that.

The same thinking scales up. It proves that any sorting method that works by comparing items needs roughly n log n comparisons. That is a famous result, and it comes from counting the squares of an extended tree.

4. Expression trees: how a calculator reads your maths

When you type (2 + 3) × 4 into a calculator, the computer turns it into a tree:

        ( × )
        /   \
     ( + )   [4]
     /   \
   [2]   [3]

Every operator (+, ×) needs exactly two numbers, and every number stands alone. Do you spot the pattern? Every node has 0 or exactly 2 children. An expression tree is naturally an extended-style tree, with the numbers sitting at the ends.

Reading the tree from the bottom up gives the answer: 2 + 3 = 5, then 5 × 4 = 20.

Quick Recap

An extended binary tree is an ordinary binary tree with an extra external node (square) hung in every empty child spot.
The original nodes are internal nodes (circles). The new ones are external nodes (squares).
Every node has 0 or exactly 2 children. That is why it is also called a 2-tree.
In every extended tree: external nodes = internal nodes + 1.
It is useful because it makes "nothing" visible and countable, and it keeps rules and formulas simple.
You meet it in Huffman coding, search analysis, sorting limits (decision trees) and expression trees.

Common Beginner Mistakes

Mixing up "leaf" and "external node". In the original tree, leaves are real nodes. After extending, those same nodes become internal, and the squares are the new leaves.
Thinking the squares are stored in memory. Usually they are not. They are an imagination tool (or just NULL). We draw them to think and count more easily.
Counting squares wrongly. Do not count by eye. Use E = I + 1. If you have 7 real nodes, you must get 8 squares. If you don't, you missed one.
Forgetting that the rule is "0 or 2". A node with exactly one child never exists in an extended tree. If you see one, you forgot to add a square.

Try It Yourself (Answers Below)

Question 1. An ordinary binary tree has 9 nodes. After extending it, how many external nodes (squares) does it have?

Question 2. An extended binary tree has 12 external nodes. How many internal nodes does it have?

Question 3. Can an extended binary tree have a node with exactly one child?

Question 4. You search a binary search tree holding 5 keys for a number that is not there. How many different "not found" endings are possible?

Answers (no peeking before you try!):

10. E = I + 1 = 9 + 1.
11. I = E − 1 = 12 − 1.
No. Every node has either 0 or 2 children.
6. That is n + 1 = 5 + 1 gaps.

See It Move: Watch It on Our Lessons

Reading is good, but watching it happen is better. On iTechnicalearning you can play these ideas step by step:

Variants of Binary Tree: build an extended binary tree and see the squares appear, plus strict, complete, perfect and threaded trees.
Huffman Trees: type a message and watch the tree and the codes being built.
Expression Trees: turn a sum into a tree and evaluate it.

Press Play, or step through with Next, and try your own examples. Each time you see a tree grow, it will make a little more sense.

One Last Thought

Extended binary trees are a perfect example of something you will see again and again in computer science: sometimes the smartest thing is to make the invisible visible.

Adding "empty seats" does not make the tree better at storing data. It makes us better at understanding it, counting it, and proving things about it. And those ideas end up inside real tools, from ZIP files to sorting limits.

So the next time a tree has a missing child, don't think of it as nothing. Think of it as an empty seat that is waiting for a story. 🙂

Happy learning, and keep building trees!