---

In linear data structure, data is organized in sequential order and in non-linear data structure, data is organized in random order. Tree is a very popular data structure used in wide range of applications. A tree data structure can be defined as follows.

Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.

A tree data structure can also be defined as follows.

Tree data structure is a collection of data (Node) which is organized in hierarchical structure and this is a recursive definition

A tree is a collection of elements called nodes. Each node contains some value or element. In a tree data structure, if we have N number of nodes then we can have a maximum of N-1 number of links. We will use the term node, rather than vertex with binary tree. Node is the main component of any tree structure. It stores the actual data along with links to other nodes.

Example

Important Terms

Following are the important terms with respect to the tree.

• Path ? Path refers to the sequence of nodes along the edges of a tree.

• Root ? The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

• Parent ? Any node except the root node has one edge upward to a node called the parent.

• Child ? The node below a given node connected by its edge downward is called its child node.

• Leaf ? The node which does not have any child node is called the leaf node.

• Subtree ? Subtree represents the descendants of a node.

• Visiting ? Visiting refers to checking the value of a node when control is on the node.

• Traversing ? Traversing means passing through nodes in a specific order.

• Levels ? Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

• keys ? Key represents a value of a node based on which a search operation is to be carried out for a node.

Tree Terminologies with Examples

Key properties of Tree

Consider the following tree. See below tree diagram from examples.

1. Root

This is the unique node in the tree in which further subtrees were attached. A root node of a tree has its child. Left child and right child are the two childes a root node can have in a tree. In the given figure A is the root node.

2. Degree of Node

The total number of subtree attached to that node is called the degree of the node. For node A the degree is 3, for node E the degree is 0.

3. Leaf Nodes

These are the terminals nodes of the tree. The nodes which have degree 0 are called as leaf nodes of the tree. These nodes are always present at the end of the tree. Here in our example E, F, C, G, H are the leaf nodes of the tree.

4. Internal Nodes

The nodes in the tree which are other than leaf nodes and the root node are called as internal nodes. These nodes are present in between root node and leaf nodes in the tree that’s why these nodes are called as internal node. Here, B and D are internal nodes.

5. Parent Node

The node which is having further sub branches is called the parent node of those sub branches. In the above figure node B is the parent node of E, F, and G node and E, F, and G are called children of B.

6. Predecessor

While displaying the tree, if some particular nodes previous to some other nodes than that node is called the predecessor of the other node. In our example, the node E is predecessor of node B.

7. Successor

The node which occurs next to some other node is called successor of that node. In our example, B is successor of F and G.

8. Level of tree

The root node is always considering at level zero, and then its adjacent children are supposed to be at level 1 and so on. To understand the concept of level, see the above figure, the node A is at level 0, the node B, C, D are at level 1, the nodes E, F, G, H are at level 2.

9. Height of the tree

The maximum level is the height of the tree. Here the height of the tree is 3. The other terminology used for the height of the tree is depth of the tree.

10. Forest

A tree may be defined as a forest in which only a single node (root) has no predecessor Any forest is consist of collection of trees.

11. Degree of tree

The maximum degree of the node in the tree is called the degree of the tree. Here, the degree of tree is 3.

---