What are the different types of Nodes in a Tree - GeeksforGeeks (2024)

Trees are nonlinear data structures that organize data hierarchically and in a recursive manner.

It is a method of organizing and storing data in the computer in a way that makes it more effective to use. Nodes in the graph are connected via edges. It has different types of nodes which are called parent node, child node, leaf node, etc.

What is a root node?

A node that is the first or topmost node in a tree is called a root node. In every tree, there is always one root node, which is the only node that has never previously been connected to another node.

Importance of root node:

• The root node, which has no parents, is the highest node in the tree structure.
• The entire message is represented by this node, which is a global element.
• It may have one or more child nodes, but it is never recurring or able to have sibling nodes.
• You can change the root node’s name.

What is a parent node?

The node which is a predecessor of another node is known as a parent node.

Or we can also say that if a node (A) is connected to another node (B) then node (A) will be known as the parent node for node (B) and similarly for other nodes as well if you refer to the below example.

• Node (A) is the parent of node (B) and node (C).
• Similarly, node (B) is the parent of node (D) and node (E).
• And node (C) is the parent of node (F) and node (G).

What is a child node?

The node which is the descendant(node which follows another node) of any node on a tree is known as a child node.

Or we can also say that every node excluding the root node is a child node in the tree. A child node always has a parent node to which it is connected. As you can see in the example below.

• Where nodes (B) and (C) are children of the node (A).
• Similarly, node (D) and node (E) are child nodes of (B).
• And node (F) and node (G) are child nodes of (C).

What is a leaf node?

A node that does not have any child node is called a leaf node.

Sometimes in this case if there is a single node (A) present in the tree then that node is also called a leaf node because of no child node connected to it. There is nothing connected to a leaf node further which is the endmost node of a tree in a direction.

What is a height of a tree?

The height of a tree is the total number of edges from a leaf node to any particular node usually a root node.

The height of a tree at the leaf node is minimum at (height of node F = 0) and maximum at the root node (Height of node A = 2).

What is the depth of the tree?

The depth of a tree is the number of edges from the root node to a particular node, usually, a leaf node and the path followed from the root node to the particular node is the longest path of a tree.

At the root node, the depth is minimum and at the leaf node, it is maximum. In the example given below at root node (A), it is 0 and at leaf node (F) it is maximum which is 2.

Let’s take one more example to clarify the concept.

What is the degree of a node in a tree?

The Degree of a node in the tree is the summation of the number of child nodes connected to it, and the node which has the highest number of child nodes in a tree is also known as the Degree of a tree.