Binary trees

A Binary Tree is a non-linear Data Structure.

Any node can have a maximum of two child nodes (which is why it's called a binary tree).

Let's look at how to organise this set of data into a Binary Tree.

Here is the above array sorted visually into a binary tree:

The first item becomes the root of the tree.
Then compare the next item with the root value. If it is less than, go left. If it is greater than, go right.
Keep comparing until an available place is found.

The following video reviews how to insert data into a Binary Tree using simulator.

If you have studied singular linked lists, you will recall that nodes in a list of nodes contain data and a pointer to the next node in the list.

Binary trees are similar but each node has:

We can imagine that if either pointer does not point to another node then it just references null or something equivalent to that.

Let's take another look at the binary tree above.

The root node is the one at the top, containing 13. It has no parent.
The nodes containing 5, 11, 16, 21 11 are considered leaf nodes - they have no children.
A parent can have 2 children, a left-child and a right-child, such as the node containing 13, 7 or 18 above.
If a node has no right-child and/or left-child, then its pointer values will null or something similar to indicate this situation.
A node in the tree, along with all of its descendents, is referred to as a subtree.

Use the simulator to create a binary tree for the following set of data:

100 , 56 , 34 , 77 , 120 , 115 , 113 , 1 , 200 , 33

As you are doing it, try to predict where each noce will be placed. How good are your predictions?!

Using a piece of paper and a pencil (or digitally if you can), construct a binary tree using the following data:

"Kansas", "Idaho", "Texas", "Massachusets", "New York", "Albaquerque", "Boston", "Wyoming", "Tallahassee", "Denver"

Annotate your tree to clearly identify:

Submit your annotated tree as instructed.

The following video will explain how to set up a Binary Tree in Python and how to search a Binary Tree for an item.

For Topic 5, this is just for background knowledge. You are not expected to code a binary tree in Topic 5 (Paper 1).

Make sure you review the Course Guide to fully appreciate what you need to know in this topic!

Useful helper video

Welcome to the hard stuff