Consider a problem, where you need to represent hierarchy. For example, organization structure. You want to represent the structure of an organization, where there are different levels such as CEO, CTO, Co-Workers, etc., where, Co-Workers report to the CTO, CTO reports to CEO.
Another example is the folder system in operating systems. Where a root folder has sub-folders, and those sub-folders have other sub-folders, and so on.
There are other Data Structures, such as Arrays, LinkedList, Stack, Queue, etc., but none of these can represent a hierarchical data. All these structures are linear, and traverse the data linearly.
10
/ \
20 30
/ \ \
35 40 15
A typical tree looks something like the above representation. This type of tree is known as Binary Tree. We will discuss about binary trees later in this article.
Let us learn some basic terminologies of a tree data structure.
Node: A node is an object of a tree, which stores the value, as well as reference to other nodes.
In the above example, a node which has a value ‘20’, and has reference to the other nodes which have value 35 and 40.
Root: The node which is at the top of the hierarchy is called root node. In the above example, node with value 10 is a root.
Leaf: The node which is at the bottom of the hierarchy is called leaf node. In the above example, node with value 35, 40 and 15 are leaf nodes.
Child: The nodes which are just one level below any particular node are called the children nodes in respect of the upper-level node. In the above example, node with value 20 has two children 35 and 40, node with value 30 has one child 15.
Parent: The node with is one level up of any particular node is called the parent node in respect to the child node. In the above example, the nodes with value 20 and 30 have a parent node with value 10, the node with value 15 has a parent node with value 30.
Subtree: A tree contains many trees inside it and these trees are called subtrees of that tree. In the above example, the tree with root node of value 10 has two children’s nodes with value 20 and 30. These nodes behave as a root node for the nodes just below it. In this case, tree with root node with value 20 is a tree for nodes 35 and 40, but is a subtree for root node with value 10.
A tree has subtrees equal to the number of nodes in that tree, because, each node can behave like a subtree in other perspective.
Descendants: These are the nodes which lie in the subtree of a node. In the above example, the descendants of the node with value 20 are 35 and 40.
Ancestors: The hierarchical nodes which are above a specific node and lie in the same tree branch. In the above example, the node with value 35 has an ancestor 20 as well as 10. This is because, 35 is a descendant of the with root node with value 20 as well as 10.
Degree: The number of children of a node is the degree of that particular node. In the above example, the node with value 10 has a degree of 2, while the node with value 30 has a degree of 1.
We can define the “Leaf” as the nodes which have a degree of 0.
Binary Tree: A binary tree is a tree with each node having a maximum degree of 2.
In Java, Binary tree syntax looks like,
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}In C++,
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};We create a self referential variable ‘left’ and ‘right’ to assign the reference (in Java) or pointer (in C++) to store the address of the left and right children nodes respectively.
There’s an other variable ‘var’ which is used to assign the value to the node.
We will explore Binary Trees, their traversal methods and some problems related to them in the upcoming articles.
