In your study of data structures, perhaps you’ve only gotten to the linear structures, e.g. stacks, queues, linked lists. Think of these as one dimensional like a street-- you can only go up or down that street. Now let’s consider a multi-dimensional data structure: trees. A tree has one main trunk, but it can have branches. And those branches can have their own branches, like this:
So what does a tree look like as a data structure?
First, let’s remember from our linear data structures that those structures consisted of nodes of data. Each node pointed to the next node:
In trees, the difference is that each node can point to more than one node:
In the above image, we have 4 nodes: A, B, C and D.
The A node is called the root, because all other nodes branch off from A. We can even say, “A is the parent of B, C and D. B, C, and D are the children of A
Siblings
Let’s learn some more terminology with this tree below:
Above, we see node A is the root and B, C , D are A’s children. However, because B, C, D are on the same level (“Same level” means you can draw a horizontal line connecting the lengths of B, C, D) these nodes are also siblings of each other.
Ancestors and Descendants
See the tree below:
In the image above, we see three nodes: A, B and E circled in pink. Just like in a family tree diagram, E’s “parent” or ancestor is B. But the “family line” extends further back to A. A is also an ancestor of E.
We can also look at it in the opposite direction with the nodes circled in blue highlighting nodes D, G, H, and I. D has two “children” or descendants: G and H. However, D’s “family line” extends further through H to I. I is also a descendant of D.
Leaves
Here’s another tree:
Sometimes nodes don’t have children. In that case, these child-less nodes are called leaves (think of a leaf on a tree blowing around in the wind untethered by any branches beyond it). A leaf can also be called external (Think of the leaf blowing in the wind as a conduit to the outside world; no further branches are blocking it.
If leafs can be termed external, what would we call those nodes who do have at least 1 child? Yep, those nodes are internal.
Path and Path Length
Given a tree where we select two different nodes of that tree, a path is the set of edges from one node to the other. The path length is the number of edges in that path:
In the above diagram, we want to get from the root, A, to H. You see the path was traced out for us in blue. Each of those arrows that point from a parent node to a child node is called an edge. We see it took 3 edges to get from A to H.
Node Level and Node Depth
Let’s describe a way to tell how deep down a given node is nested:
In the image above, we define the root level to be “0”. Each succeeding level increases by 1. The terms “level” and “depth” are used interchangeably.
For example, we see that Node C is at a depth (or level) of 1. Node H is at a depth of 3.
Another related concept is the height of a tree:
In this example, we can determine the height of a tree by just counting levels--the trick is that we have to start with “0”. So node A is at a height of 0; B, C, and D are at a height of 1. E, F, and G are at a height of 2 and finally node H is at a height of 3. Our tree’s height is then 3.
Degree
Look at this example:
First of all its height is 2. Can you tell?
Then, we look at the maximum number of possible children for every node in the tree. We see that the maximum number is 3.
We can say that our tree has a height of 2 and a degree of 3.
Types of Trees
The last thing we’ll look at today are types of trees.
You can have a tree where each node has any number of children from 0 to n. The number of children each node has can be different from parent node to parent node. In this case, we have a general tree
On the other hand, we can have a tree where every parent has at most n children. The most popular version of this kind of tree is where n = 2. In this case we have a binary tree.
Here’s an example of a binary tree:
Notice how we have the root at node 1. Then each child or descendant of node 1 has at either 0, 1 or 2 children.
So there you have most of the basic terminology to be able to work with trees. Most of our work going forward will be with binary trees--as my tutor told me, binary trees represent about 95% of the work with trees.
More to come!
Keep coding out your dreams!
Namaste!
Top comments (0)