Binary Trees: Structure, Properties, and Traversals, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 12.2 Free with a free account

Binary Trees: Structure, Properties, and Traversals

Data Structures and Algorithms · Chapter 12: TreesSection 12.2 · lesson 50 of 8712 min · free with a free account

← Why Hierarchies Represent Nested RelationshipsNext lesson: Choosing the Right Tree: Layouts and Applications →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Binary tree nodes, height bounds, array layout and four traversal orders.

  • Describe binary tree nodes and classify trees as full, complete or perfect
  • Calculate the maximum nodes for a height and the height range for n nodes
  • Map a binary tree onto an array using index arithmetic
  • Trace preorder, inorder, postorder and level-order traversals

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,833 words). Read along, or search it.

Opening Question

Same Values, Very Different Heights

Two binary trees each hold the same million values. In one, the longest path from the top to the bottom is nineteen steps. In the other, it's nine hundred ninety-nine thousand, nine hundred ninety-nine steps. Same values, same code. So what makes the difference? The answer is the shape of the tree, and by the end of this lesson you'll be able to predict it.

Definition

Left Child and Right Child

A binary tree is a tree in which each node has at most two children, and they are told apart: the left child and the right child. So a node with only a left child, and a node with only a right child, are two different trees. In Java, a tree node is the linked list node with a second reference. Instead of one next, it holds left and right, and a missing child is stored as null.

Worked Example

Building the Sample Tree

Here's the tree used for the rest of this lesson. The root holds ten. Its left child is twenty, and its right child is thirty. Twenty has two children, forty and fifty. Fifty has a left child, seventy. And thirty has only a right child, sixty, which is perfectly legal. No node was told about its parent. Each one knows only its two children, so the whole tree is reached from one variable, root, just as a list is reached from its head.

Vocabulary

Root, Leaves, Levels and Subtrees

Now the vocabulary, on this tree. Ten is the root. Forty, seventy and sixty have no children, so they're the leaves. Ten, twenty, fifty and thirty each have at least one child, so they're internal nodes. The level, or depth, of a node is its number of edges from the root. Seventy sits on level three, and the tree's height is three. And a subtree is a node with everything below it, like twenty, forty, fifty and seventy.

Convention

Counting Height in Edges

One warning about height. This course counts edges, so a single node has height zero, and the empty tree has height minus one. Some books count nodes instead, and get a number one larger. Always check which convention a source uses.

Node Count Limits

At Most Two to the k per Level

How many nodes can a binary tree hold? Each node has at most two children, so each level holds at most twice as many nodes as the level above. Level zero holds at most one node, level one two, level two four, and level k at most two to the k. Add the levels up, and a tree of height h holds at most two to the h plus one, minus one, nodes. The fewest is h plus one, in a chain where each node has one child.

Height Bounds

Between Log n and n Minus One

Read the other way, that bounds the height of a tree with n nodes. The shortest possible is the floor of log base two of n, when each level fills before the next one starts. The tallest is n minus one, a chain. With a million nodes, that's a height between nineteen and nine hundred ninety-nine thousand, nine hundred ninety-nine. That's the answer to the opening question. Same values, very different shapes, and every path from the root costs its height. Keeping trees short is a theme for the rest of the course.

Tree Shapes

Full, Complete and Perfect

Three names describe how tightly a tree is packed. A full tree: every node has zero or two children, never exactly one. A complete tree: every level is filled except possibly the last, and the last level's nodes are as far left as possible. A perfect tree is full, with all its leaves on the same level. Every perfect tree is also complete, but apart from that, full and complete are independent.

In Code

Recursive Shape Tests

In code, each rule becomes a short recursive test. Is full checks that no node has exactly one child. Is perfect compares the node count with the most a tree of that height can hold. And one more fact holds in every full tree: it has one more leaf than internal nodes.

Quick Check

Nodes Needed for a Perfect Tree

Quick check. A new tree has five nodes. The root has two children. Its left child has two leaf children, and its right child is a leaf. How many nodes would you have to add to make it a perfect tree? Pause, and decide. It's b: two more. The tree has height two, and a perfect tree of height two holds two cubed minus one: seven nodes. C is a leaf one level higher than D and E. Give C two children, and every leaf sits on the same level. Right now the tree is already full, since every node has zero or two children, and complete, since its last level fills from the left. It just isn't perfect.

Array Storage

Children Found by Index Arithmetic

A tree can also live in a plain array. Number the positions level by level, left to right, starting at zero. No references are needed, because a node's relatives follow from arithmetic. The children of index i sit at two i plus one, and two i plus two. Its parent sits at i minus one, over two, with integer division. So both children of index one, at three and four, give the same parent: one. Counting from one instead, the formulas become two i, two i plus one, and i over two, a variant common in textbooks.

Trade-Off

Wasted Slots for Unbalanced Shapes

The array is compact when the tree is complete: n nodes need exactly n slots. Other shapes waste slots. A chain of five nodes that always goes right has height four, so it needs thirty-one slots, and uses only five of them: zero, two, six, fourteen and thirty. A chain of ten nodes would need one thousand twenty-three slots. The linked form handles any shape, but a node can't find its parent. The array finds parents by arithmetic.

Traversals

Preorder, Inorder, Postorder and Level Order

A list has one natural order. A tree has none, so a program that visits every node must choose an order, called a traversal. Three are depth first: they go all the way down one branch before starting another, and differ only in when the node itself is visited. Preorder visits the node, then its left subtree, then its right subtree. On the sample tree: ten, twenty, forty, fifty, seventy, thirty, sixty. Inorder visits the left subtree, then the node, then the right: forty, twenty, seventy, fifty, ten, thirty, sixty. Postorder visits both subtrees, then the node: forty, seventy, fifty, twenty, sixty, thirty, ten. The fourth, level order, is breadth first. It goes level by level, left to right: ten, twenty, thirty, forty, fifty, sixty, seventy.

In Code

Moving the Print Line

Each child is the root of a smaller tree, so the three depth first orders are natural recursive methods. The base case is the empty tree: null. Here's preorder. If the node is null, return. Otherwise print the node, then traverse left, then right. Inorder and postorder are the same method, with the print line moved to the middle, or to the end. Move it, and you get a different traversal.

Cost

Calls, Missing Children and Stack Depth

How much work is that? A counter in preorder showed fifteen calls for the seven nodes: one per node, plus one for each of the eight missing children. A tree with n nodes always has n plus one missing children, so a traversal makes two n plus one calls. That's order n. And the calls waiting on the stack always form one path down from the root, so the stack depth is about the height. On a balanced tree of a hundred thousand nodes, the height was sixteen. On a chain of a hundred thousand, a recursive height method crashed with a stack overflow error.

Level Order

A Queue Visits Level by Level

Level order can't be a simple recursion, because it has to remember a level's nodes while it visits earlier ones. A queue does exactly that. Visit the node at the front, then add its children to the back. Start with ten. Remove it, and add twenty and thirty. Remove twenty, add forty and fifty. Remove thirty, add sixty. Then forty, fifty, which adds seventy, then sixty and seventy. On this tree, the queue never holds more than three nodes, and each node is visited once, so level order is order n as well.

Quick Check

Predicting a Postorder Sequence

Quick check, with a new tree. The root is five. Its left child, two, has a left child, seven. Its right child, nine, has children four and one. In what order does postorder visit the nodes? Pause, and predict. It's a: seven, two, four, one, nine, five. Postorder finishes both subtrees before the node, so the root, five, comes last. Option b is preorder, root first. Option c is inorder, root in the middle.

Choosing an Order

Which Traversal for Which Job

Which order when? Preorder puts a parent before its children: use it to copy a tree, or list a hierarchy from the top down. Postorder puts children before their parent: use it when a node's answer depends on its children, like sizes and heights, or when a tree is being discarded. Inorder gives the left to right order as drawn. On the sample tree that's not sorted. When it is sorted depends on an ordering rule, which comes with search trees. And level order puts the nodes nearest the root first. Use it when a node's level matters.

Recursive Methods

Size, Height and Leaf Count

Size, height and leaf count all follow one pattern: handle the empty tree, then combine the left and right answers. Size of an empty tree is zero, else one plus the two sizes. Height of an empty tree is minus one, else one plus the larger height. Leaves of an empty tree is zero. A node with no children counts one, and otherwise you add the two counts. On the sample tree: size seven, height three, leaves three. Minus one makes a single node come out as zero, since one plus minus one is zero. And each method asks its children first: that's the postorder pattern.

Common Mistakes

Null Checks, Height Base and Stack Overflow

Three mistakes to avoid. Forget the null check, and the recursion throws a null pointer exception the moment it reaches a missing child. Use zero as the height of the empty tree, and every height comes out one too large: the sample tree gives four. And recurse on a very tall tree, and the stack overflows. Keep trees short, or use an iterative method like the queue version.

Key Takeaways

Nodes, Bounds, Arrays and Traversals

To recap. A binary tree node holds a value and two references, left and right, and null means no child. A tree of height h holds at most two to the h plus one, minus one, nodes, and n nodes give a height between log n and n minus one. In an array, index i has children at two i plus one and two i plus two, which wastes space unless the tree is complete. Preorder, inorder and postorder differ only in when the node is visited. Level order uses a queue. Each one is order n.

Think About It

Why Recursion Fails on a Chain

Here's something to think about. A recursive height method works on a balanced tree of a hundred thousand nodes, but fails on a chain of a hundred thousand. Same number of nodes, same code. Why do they behave differently? And would level order, with its queue, fail on the chain too?

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Binary Trees: Structure, Properties, and Traversals

How many nodes can a binary tree of height h have?
A binary tree of height h holds at most 2^(h+1) - 1 nodes, because level k holds at most 2^k nodes and the levels add up. It holds at least h + 1 nodes, in a chain where each node has one child. Read the other way, n nodes give a height between floor(log2 n) and n - 1. With a million nodes, that range runs from 19 to 999,999.
What is the difference between preorder, inorder and postorder traversal?
They differ only in when the node itself is visited. Preorder visits the node, then its left subtree, then its right subtree. Inorder visits the left subtree, the node, then the right subtree. Postorder visits both subtrees before the node. For a root 5 whose left child 2 has a left child 7, and whose right child 9 has children 4 and 1, postorder gives 7, 2, 4, 1, 9, 5.
How do you store a binary tree in an array?
Number the positions level by level, left to right, starting at index 0. The children of index i sit at 2i + 1 and 2i + 2, and its parent sits at (i - 1) / 2 with integer division. A complete tree with n nodes uses exactly n slots. Other shapes waste space: a five-node chain that always goes right occupies indexes 0, 2, 6, 14 and 30, so it needs 31 slots.
Why does a recursive binary tree method cause a StackOverflowError?
Each recursive call waits on the call stack, and the waiting calls form one path down from the root, so stack depth grows with the tree's height. A balanced tree of 100,000 nodes has height 16, which is harmless. A chain of 100,000 nodes has height 99,999, which can overflow the stack. Keeping trees short, or using an iterative method such as level order with a queue, avoids the problem.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →