Trees — the data structure

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:

And this is also a tree:

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.

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

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.

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.

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.

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.

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?

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.

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

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.

In-Order Traversal

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.

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!

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.

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

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:

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

Postfix notation looks like:

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.