Let’s talk about one of the most important Data Structures out there, the one which helps organize and store Data in efficient and effective manner. Tree is non-linear and hierarchical Data Structure, it consists of Nodes storing values in Parent-Child relations. Node containing children is considered to be a parent, just like in a typical family.
Components Of the Tree
Vocabulary which comes with this DS is quite extensive. I think this is a good idea to start with a drawing.
As you can see there is a lot to grasp. Depending on its relation and position, Node has some properties attached to it. Let’s dissect them.
Relation To Other Nodes
Nodes in the Tree have relations between them and routes which make it possible to move around the structure. Let me introduce you to how they form families and paths.
Family Of Nodes
Have you ever seen a plant called tree? If so, you must be aware that trees grow from the ground up and to keep them steady and strong in the ground they need a Root. In a Tree DS there is also a root, it is a Node on the top which doesn’t have any Parent, but is a Parent itself. It always occupies Level 0 of the Tree.
Parent’s descendant is called a Child. Node 2 is a Child of a Root Node 1 being Parent for Nodes 4 and 5 at the same time. Children of the same Parent, being on the same Level are called siblings. They can also be Parents, just like in the real life. There are also Nodes which don’t have any children, childless one is called a Leaf and one having at least one Child is called an Internal Node.
Last relation I need to mention is a Neighbour. This is an umbrella term for every Parent and Child of a particular Node.
Path
The distance between some Nodes within a Tree is called a Path. Length of Path is determined by the quantity of Nodes which form the Path. It is represented by values connected with hyphens, the longest path for example looks like this: 1-3-7-15-16. The length of this Path equals 5.
Position In The Tree
Based on the Node’s position within a Tree we can think of three properties it comes with, like Depth, Height and Level. Let me shed some light on them.
Node Depth
Depth is a measurement of how many Edges are there between Root and a given Node. Root has always depth equal to zero. Why zero? Actually Tree DS is represented upside-down where root is always on top. It may be misleading when reasoning about Depth because in real life root is always at the bottom. Look at the Node 7, there are two Edges between this and Root, so the Depth of Node 7 is equal 2. It concerns every Node on a given Level.
Node Height
Height tells us how many Edges are there on the longest path from that Node to its furthest Leaf Node. This Leaf always has height equal 0. Every Edge on the way adds 1 to the total value of Height. In our case the longest path is between Root and Leaf Node 16 and Root’s Height is 4.
Node Level
When thinking about Level we must count Edges between Root and its particular Child. Root is always on Level 0. There are two Edges between Root and Child Nodes 4, 5, 6 and 7, so it positions them on Level 2. The furthest Leaf Node 16 is placed on the Level 4 because there are four Edges between this and Root.
Tree Within A Tree
If any Child in the Tree contains at least one Child then it forms a Subtree. You can see the example of such Tree within a Tree on green Nodes: 6, 12 and 13.
When it comes to Subtrees there is a measurement called Degree of a Node. It tells how many Subtrees are attached to particular Node. Leaf will have Degree equal to zero based on its definition. If you take a look at Figure 1 on Node 7 you will notice that Degree is two, because there are two children: 14 and 15.
Hanging In The Balance
We say that Tree is balanced when right and left subtrees’ heights differ by no more than one Node and both of them are also balanced. Picture above presents a balanced Tree, the difference in heights is exactly one. You can see the example of the unbalanced Tree below.
The difference in heights between left and right Subtree equals 2, thus this Tree is unbalanced.