Understanding the tree data structure
In the last journal of data structure, I concluded the linked-list data structure and its time for a new data structure topic: ’Tree.’
What is a tree?
The word itself is pretty self-explanatory; a tree data structure is similar to the model tree in real life. A tree in data structure consists of nodes(just like in linked list), but they are in a parent/child relationship. Usually, in a tree’s data structure diagram, it starts with a root on top, which is the opposite in a real-life diagram. A tree data structure doesn’t store data linearly, such as a single-linked list (one path /one line), but in non-linear(hierarchically). A tree data structure branches out more than one pathway (multiple lines/paths).
A tree data structure in real life could be something like a family tree or corporate ladder.
There are a lot of tree data structures in the computer world. For instance: HTML DOM, Network Routing, Abstract syntax tree, Artificial Intelligence, Folders in Operating Systems, computer file System, JSON parsing.
Tree basic terminology
- Root: First node of the tree, the top node in a tree.
- Edge: The connecting between one node and another.
- Child: A node directly connected to another node when moving away from the root
- Parent: Anode that has an edge to a child node(the converse notion of a child)
- Siblings: A group of nodes with the same parent
- Leaf: A node with no children
- Height: The length of the longest path to a leaf (going down)
- Depth: The length of the path to its root (going up)
Fundamental rules of tree data structure
- A node can only point to a child, not siblings or parents.
- Every tree must have a root node and only one root, not multiple root nodes in a tree.
Ther are different types of trees data structure. In the next Journal, I will be implementing one of the most popular types of tree data structures ( binary search tree spoiler alert) from scratch. So stay tuned for that one, and as always, thanks for reading, and I hope you enjoy it!