Learn About Binary Trees
Remember linked lists? Now imagine that each node contains two addresses rather than one. If we were to represent it as a diagram, it would look something like a tree. This is what’s known as a binary tree.
Like in a family tree, there’s one parent cell, and all the rest are child cells. In a non-empty tree, there’s only one cell which doesn’t have a parent cell, which is called the root of the tree. All the other cells stem from the root.
Binary trees are very widely used in IT, as they’re considered to be the simplest and most efficient data structures to use in most computer systems. They probably still seem like an abstract concept to you, but they’re used in all sorts of common settings:
3D video games
Internet routers
Databases
Calculators
As you can see, binary trees are everywhere! It’s therefore important to understand how they work.
Why is it called a binary tree?
Simply because each parent cell has zero, one, or two child cells, which in turn are linked to other cells.
In tree terminology, the cells are called nodes or vertices. A node with no child is called a leaf node.
In other words, a binary tree is a bit like a linked list, except that each cell has up to two child cells. These are referred to as the left child and the right child. However, a node doesn’t necessarily have to have any child cells.
Binary Tree Traversal
To find information in a binary tree, you need to search all of its nodes in a process known as tree traversal. But how? The simplest way is to use a recursive function.
What’s a recursive function?
Recursion is a process which makes sense when the solution to a problem hinges on a smaller problem being resolved. It involves a function calling itself, in a loop, until it reaches the condition which stops it from calling itself again, known as the “base case.”
Don’t worry, there’s a specific chapter on recursion in the next part of the course! For now, you only need a basic idea of this concept.
There are many ways to search a tree, depending on the order of examination of the nodes.
Learn About Graphs
A graph is a set of cells linked in a different way to trees—they use a type of link known as edges. They look like a set of nodes or vertices linked by lines.
A graph can represent a road network, an air transport network, an IT network, and many other things.
Graphs are often used by algorithms to find the shortest route between point A and point B. One example we all know which uses this principle is Google Maps. Facebook also uses graphs to introduce you to friends of your friends!
On Facebook, each person in the network is represented by a circle (also known as a vertex). Your friends are linked to you by lines (called arcs). People you might be interested in meeting are those linked to your friends by an arc. It’s as simple as that!
Let’s Recap!
A binary tree is a special data structure used for storing data.
A binary tree provides all the advantages of both a sorted array and a linked list.
Binary trees are made up of nodes and children—each node can have up to two children.
A graph is a representation of a set of objects, in which certain pairs of objects are linked.
The linked objects are represented by points which are called vertices, and the lines linking the vertices are called edges.
You’ve learned a lot in this second part! Now it’s time to put your new skills to the test with a quiz. Good luck!
