Trees — the data structure

Brandon Skerritt
May 4, 2018 · 6 min read

A tree T = (V, E) consists of a set of vertices (V) and a set of edges (E).

The vertices are the “Nodes” in a tree and the edges are the “lines connecting them”.

This is a tree:

Image for post
Image for post

And this is also a tree:

Image for post
Image for post

Tree’s have exactly one path between two vertices. You cannot have more than one path between any 2 vertices.

The number of paths that lead into and out of a vertex is called the degree of a vertex.

A cycle is where you can “Move all the way around”. Notice the vertices y, u, and v. You can “move all the way around” these 3 vertices. Acyclic means there is no cycle in the graph. If it is Acylic it implies it is a tree.

If it has more than 2 paths from 1 vertex to another or it has a cycle then it is not a tree.

Image for post
Image for post

A tree is often used to represent something that has a hierarchical sturcture, such as files and folders in a desktop.

Image for post
Image for post

A rooted tree has a direction where it goes from the top to the bottom but in some cases we can have an unrooted tree where it is not drawn top to bottom.

The topmost vertex is called the root of the tree. Where it all comes from.

Image for post
Image for post

A vertex might have children below it, connecting to the vertex. In this case we say the ones below it are the children / child and the original vertex is the parent of the vertex.

Image for post
Image for post

In a rooted tree there is an implicit direction of the tree that is often not drawn in rooted trees, usually it goes downwards.

The degree of a vertex is the number of children it has.

The degree of a tree is the max degree from a vertex in the tree. So if a vertex has a degree of 3 and no other vertex has a degree higher than 3 then the degree of the tree is 3.

Image for post
Image for post

A vertex with no children (degree 0) is called a leaf.

Vertices other than leaves / roots are called internal vertices. These are sometimes called downward branches in a rooted tree.

A subtree is a tree that comes from a vertex that isn’t the root vertex. You can have a subtree of a subtree.

Image for post
Image for post

Any vertex can be considered a sub-tree with 1 single leaf in it.

Binary Tree

A binary tree has a degree of most 2. No vertex has a degree higher than 2. The two subtrees are called the left subtree and the right subtree.

The left hand side tree is smaller, the right hand side tree is larger. This is a really cool feature of binary trees. Binary trees are based off of comparisons. Is one number bigger than another number?

Image for post
Image for post

We start off with the root node, which in this case is 20. Let’s say we wanted to insert the numbers 10 and 3 into the tree. 3 is less than 10 so it goes on the left hand side.

Image for post
Image for post

Now we inset a few mode nodes for some data. Smallest of the 2 compared always goes left, largest always goes right.

Image for post
Image for post

Now what if we wanted to find the number 8?

Start off at 20. Is 8 larger than 20? No. So it’s not on the right hand side. We just halved the entire tree. We don’t need to check the right hand side at all in order to find out if 8 is in the tree. Okay, so is 8 larger than 3? Yes it is — so 8 must be on the right subtree.

And yes, we found 8! So easy and fast!

You can traverse binary trees using these 3 algorithms, but note that these only work on binary trees because we need to have a “left” subtree and a “right” subtree.

Pre-Order Traversal

A pre-order traversal method visits the left subtree first, then the left and right subtrees of that subtree the right and then eventually the right subtree. It tries to go down as far left as possible and stick to the left hand side as much as possible.

Image for post
Image for post

In-Order Traversal

Image for post
Image for post

In-order traversal gives us numbers in ascending order, which is a really cool feature of this traversal.

Post-Order Traversal

We first traverse the left subtree, and then the right subtree, and then finally the root node. The root node is visited last.

Image for post
Image for post

Post-Order Traversal gives us the postfix notation of a mathematical equation.

What if you forget which one’s which?

Luckily there’s this “dot” notation you can use!

Image for post
Image for post

So, firstly you need to know these dot positions. They’ll come in handy in a second!

So let’s say you want to find the the pre-order traversal, you put the dot to the left of the node like in the picture above.

Image for post
Image for post

Then you write S on the left hand side of the root node and F on the right hand side of the root node.

Now you simply draw a line from S to F

Image for post
Image for post

Try not to go back on yourself. We could of gone to 6 and then 5, but that would of made a mess and it would be hard for us to go back on ourselves without the lines looklikg like they touch.

Expression Trees

A mathematical expression can be expressed as a tree like so.

In fix notation is written as:

Image for post
Image for post

This is what we normally use. The operator (addition, multiplication) is in the expression.

Postfix notation looks like:

Image for post
Image for post

We can use post-fix traversal to get the postfix notational representation of equations.

The operator is at the end of the expression it is evaluating. Computers often use this notation more than in-fix notation.

If we look at the in order traversal for the expression tree we get the in fix notation. If we want to get the post fix we need to use post order traversal.

Notes on Computer Science

Ever wanted to learn computer science?

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store