The tree is a nonlinear data structure and a very important part of computer programming. It is a very flexible, versatile and powerful data structure.
The tree can be used to represent data items possessing hierarchical relationships. Items in a tree are arranged as interconnected nodes and edges.
There is a special data item known as root and rest are known as subtrees. This segment is based on the Tree data structure Interview Questions asked in various programming interviews.
The tree data structure is an important part of data structure and played a very vital role in solving complex problems.
This segment is based on concepts and theory of Trees Data structure and very helpful for fresher candidates in an interview.
What are the main applications of Trees?
A tree is a hierarchical representation of data and a non-linear data structure. Hence it has application according to its properties :
- To Represent hierarchical data
- To Store data in a sorted fashion
- To make the searching process easy
What is root?
The first item in the hierarchy is known as the root and it is placed at the top of the tree. A root is known as root is known and it is a terminal node having a degree greater than zero.
What is a node?
Each item in a tree is known as a Node. Nodes are connected to each other and hence they have a degree.
What is the degree of node?
The degree is known as the connectivity of a node. The number of subtrees connected to a node is known as the Degree of Node.
In the Given Tree :
- Degree of A = 3
- Degree of B = 0
- Degree of D = 2
- Degree of E = 0
- Degree of F = 0
What is the Degree of Tree?
There are several nodes in a tree data structure.
Each Node has its degree, the number of the connected subtrees.
The degree of the node having the maximum degree is Known as the Degree of Tree.
For Example in the above tree, the Degree of Tree is 3, because the degree of Node A is 3 and It is maximum.
What are siblings?
Nodes having common parents are siblings.
We can say the nodes remain at the same level in a tree are siblings if they are connected to a common node.
The common node is known as Parent.
For Example, D is parent and E and F are siblings.
What is the edge?
The line which is connecting two nodes is known as Edge.
What is the path in a tree?
If we select a node as the source and another as a destination node, then the sequence of the node between these two nodes is known as path.
- There may be many possible sequences so there may be many paths between two nodes.
- The path is represented as node pairs. For example, in the given Tree structure the path between A and G is (A, D) (D, E) (E, G).
What is a forest?
The set of Disjointed trees is known as a forest.
When several subtrees are there and they are not joined by a root then this set is known as a forest.
What is a binary tree?
A tree is a special case of a tree when any node can not have more than 2 children.
Each node can have at most two children.
We can structure a binary tree in three parts
- Left subtree
- Right Subtree
How many types of binary trees are there?
The most popular types of binary trees are as follows :
- Full Binary Tree
- Complete Binary Tree
- Perfect Binary Tree
Full Binary Tree
A Binary Tree will be known as the full binary tree if each node of the tree has either two children or zero children.
The node having zero children is known as a leaf node, so a Full Binary tree is a tree where all nodes have two children except the leaf nodes.
A binary tree having every level is completed except the leaf nodes,
Perfect Binary Tree
In a Perfect Binary tree, all the internal nodes have two children and all the leaf nodes are at the same depth.