Introduction to Trees

We have learned data structures like arrays, ArrayList, stacks, queues, etc.? So, what is common between all these data structures?

They all are linear data structures, i.e., the memory allocation of these data structures is linear. But, in real life, we often do not want the data to be stored linearly. Therefore these data structures can’t be enough for us. In such cases, we make use of the tree data structure.

Tree

Let us take an example of the folders inside a laptop. Consider, inside the “C drive” of the laptop, we have two folders. One of them is named personal, and the other is named work. The personal folder has three folders inside it, i.e., “Family Pictures,” “Bank Details,” and “Passwords,” whereas the work folder has two folders inside it, “Tasks” and “Team Members.”

In the example, the personal and work folders are inside the “C drive.” So, the C drive comes first, and it can be called the parent of the personal folder and the work folder. So, this type of data arrangement where hierarchy is involved can be stored using a data structure called the tree data structure.

The tree is a discrete data structure representing hierarchical relationships between individual elements or nodes.

Tree (Source: https://www.programiz.com/dsa/trees)

Important Terminologies

Tree (Source: https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm)

Parent Node: The node connected to one or many nodes in the next hierarchical level (i.e., the level below this node).

Child Node: The node connected to one node in the previous hierarchical level (i.e., the level above it).

Root Node: The node at the top of the hierarchy level in a tree with no parent node and all the other nodes descended from it is called the root node.

Leaf Nodes: All the nodes that do not have any child nodes are called the leaf nodes. It may or may not necessarily be at the lowest level).

Ancestors of a Node: All the nodes from which a particular node is inherited.

Descendants of a Node: All the nodes that descend from a particular node. All the nodes in the sub-tree descended from a node are its descendants.

Sibling: The nodes that have the same parent are known as siblings.

Now that you have learned the basics of trees, check out the problems like the largest number in a binary tree, deepest leaves sum, sum tree to leaf numbers, etc, at Leetcode.

Frequently Asked Questions

1. What is a binary tree?

A binary tree is a unique data structure used for data storage purposes. In this, each node can have a maximum of two children. It has the benefits of both an ordered array and a linked list, as search is as quick as in a sorted array, and insertion or deletion operations are as fast as in the linked list.

2. What is a generic tree?

If the maximum number of child nodes of a tree is not fixed and it can have as many child nodes as possible, then it is called a generic tree.

3. Why is a tree called a non-linear data structure?

A tree data structure is called a non-linear data structure because it does not store sequentially. It is a hierarchical structure as elements in a tree are arranged on multiple levels.

4. How can we calculate the height of node x?

The height of node x can be defined as the longest path from node x to the leaf node.

That’s it from my side. I hope you found this post useful 😊.

For reference, check out the GitHub Repo. Feel free to star this repository ⭐.

Let’s get connected on Github/LinkedIn/Website/Twitter/Quora ;)

And if you have any suggestions, feel free to get in touch with me over LinkedIn & the comment section is also all yours.

If you liked this story, hit the clap button as it motivates me to write more & better.