Continued reviewing the terminology used to describe the properties and functions of the tree data structure. Wow I wish I had done this sooner. It really cleared up a lot of questions that I had back when I was covering Big O notation. Maybe it would have been slightly better to cover data structures before covering Big O notation. I am not sure it’s sort of like the “chicken before the egg” debate.

TLDR;

Okay, so here are the highlights of what I did:

• Continued work on the “Technical Questions” section of the book “Cracking the Coding Interview” by Gayle Laakmann McDowell. I continued my work on Tree data structures. I continued writing my notes covering the terminology used to describe the properties of trees. Next up is looking at some code and some implementation tutorials. Step by step I’m building up my knowledge base and it feels great!

Terms for trees

Definition of a Tree Data Structure

A Tree is defined as a collection of entities called nodes, linked together to simulate a hierarchy. Unlike linear data structures like stacks, queues, and linked lists, a tree is a a non-linear data structure. A tree is a hierarchical data structure. A tree is also a recursive data structure.

What types of Data are Trees Used For

Trees are often used for hierarchical data like company hierarchies and computer files and folders.

• File systems
• Organizing data for quick search, insertions, and deletion
• Tries (a special type of tree) are used for dictionaries
• Network routing algorithms

Terms for trees

Nodes

A node is an entity that exists in the tree data structure. Each node holds a value alongside information for it’s parent node, and child nodes. We often want to know the number of nodes that exist in any given tree.

Edges

An edge is the link between two nodes. All nodes except for the Root Node have one incoming link to a Parent Node and can optionally have outgoing links to child nodes beneath them. The Root node has no incoming link to a parent node because it is the root (start) of the tree.

Therefore, since all but one node has a link / edge we can say that there are always N - 1 number of edges if there are N number of nodes.

The Depth of a Node

The depth of a node in a tree can be described as the length of the path from the root of the tree to the desired node. It is equal to the number of edges in the path from the root of the tree to the desired node.

For example the depth of the root node in any tree is 0.

The Height of a Tree/node

The height of a tree is calculated by counting the number of edges in the longest path from the root node to a leaf node (the height of the root node is the same as the height of the tree). The height of any node is calculated by counting the number of edges in the longest path from the node to a leaf node. For example:

    1
   / \
  2   3
     /
    4

The height of node 3 is 1 because the leaf node 4 is the only option for the longest path from the node to a leaf node. The height of the root node 1 is 2, with the longest path going to the leaf node 4. Therefore the height of all leaf nodes is 0. The height and depth of a node may not be the same.

The Root of a Tree

The starting node of the tree (The Topmost node in the tree). This node has no parent. If the tree has more than one node then the root is the parent, grandparent, or ancestor of all other nodes and leaves in the tree.

A Parent Node

A parent node is a node that has child nodes that exist under it. For example, in the tree below, node 1 is a parent node to both node 2 and node 3.

    1
   / \
  2   3

A Child Node (Children)

A child node (children nodes) are nodes that exist directly below their parent node. They are referred to as the children of the parent node. For example, in the tree below, node 2 and node 3 are both child nodes (children) of node 1.

A Leaf Node

A leaf node is a node that has no children. For example in the tree below, node 2 and node 3 are both leaf nodes.

    1
   / \
  2   3

A Sibling Node

A sibling node is a node that share the same parent as the node it is being compared to. For example, in the tree below. Node 2 and node 3 are sibling nodes because they share the same parent node which is node 1.

    1
   / \
  2   3

Additional Terms for relationships of Nodes

There are multiple other terms that share a familial usage and can be applied similarly in Trees

• ancestor
• descendent
• grandparent
• cousins

Conclusion

That’s all for today. This is my sixth round of the “#100daysofcode” challenge. I will be continuing my work from round five into round six. I am currently working through the book “Cracking the Coding Interview” by Gayle Laakmann McDowell. My goal is to become more familiar with algorithms and data structures. This goal was derived from my goal to better understand operating systems and key programs that I use in the terminal regularly e.g. Git. This goal was in term derived from my desire to better understand the fundamental tools used for coding outside of popular GUIs. This in turn was derived from my desire to be a better back-end developer.

I have no idea if my path is correct but I am walking down this road anyways. Worst case scenario I learn a whole bunch of stuff that will help me out on my own personal projects.