Tree in Data Structure | DSA Tutorials

Tree in Data Structure – A tree is a nonlinear data structure that represents the hierarchical relationship among its elements.

Tree in Data Structure?

A tree is a finite set of nodes such that there is always a distinguished node called a root. and other nodes are partitioned into subtrees.

Types of Trees

1. Binary tree
2. Strictly binary tree
3. Extended binary tree
4. Full binary tree
5. Complete binary tree

But before we get into the details of each one of these trees, first, we need to understand some basic terms about trees.

What is a Node

Each element of the tree is called a node of the tree. As you see in Figure 1, every element like S, O, and Q is a node. 

What is Edge

The lines connecting the nodes are called edges. The line connecting the nodes T and S is called an edge of the tree.

What is Parent Node

The immediate predecessor of a node is called the parent node. Like T is the parent of nodes S, O, Q, and M, because T is the immediate predecessor of nodes S, O, Q, and M.

What is a child node?

The immediate successor of a node is called the child node. like the nodes S, O, Q, and M are child nodes of Node T.

What is the root node?

A node that doesn’t have any parent node is called the root node. Like Node T doesn’t have any parent node, so it is a root node of the tree.

What is the Leaf node?

The node that does not have any child nodes is called a leaf node. Like the nodes, E and N don’t have any child nodes, so both are called leaf nodes.

What is the level of the tree?

The distance of that node from the root is called the level of the node. Here in the example, there are four levels.

What is the Height of the tree?

The total number of levels in a tree is called the height of the tree. Like in the above example, the tree has four levels, so the height of the tree is four.

What are Sibling Nodes?

Two or more nodes that have the same parent node are called sibling nodes. Like the nodes, E and N have the same parent node, F, so both are siblings of each other.

What is the Path in the tree?

The sequence of nodes in which each node is the parent of the next node is called the path in the tree. Like in the above example, path TSFE is a path in the tree.

What is the Ancestor node?

Node A is the ancestor of node B if node A lies in the unique path from the root node to node B. Like in the above example, node S is the ancestor node for F, G, H, E, N, and C nodes.

What is the Descendent node?

If node A is the ancestor of node B, then B is the Descendant node of node A. Like in the above example, nodes F, G, H, E, N, and C are descendant nodes of node S.

What is Subtree?

A subtree is a part of the tree, and in a tree, there is a minimum of one subtree.

What is the Degree of the node?

The number of subtrees or children of a node is called the degree of a node. So in the above example, the node tree has a degree of 3 because the maximum number of children is 3, which is connected to node T.