Data Structure – Trees

When you read the word Tree. What becomes in your mind first?

Ans. We can say that firstly root and stems become in our mind. Similarly, Trees in Data structure. Which have one route node (like the root of the tree) and many different node belongs to that rote node (like stems of the tree). Structure says the arrangement technique of anything. But here we will go to discuss the data structure, which means the arrangement of data in the format of a Tree structure.

Tree

Tree

The tree is a hierarchical data structure. It means the root expands in a hierarchical form that has a non-linear structure. Example- family. A tree “T” is a finite set of different types of nodes.

• It has a special node called root node R of the tree.

• After the root node, the remaining nodes partitioned into disjoint sets. T1, T2, T3………..Tn. (where n>=0). In which each set of the tree (T1, T2, T3……Tn) called subtree of the root node R.

Tree Structure

How many elements used to make a tree ?

Elements of the tree are –

  • Root – Root is a node that has no parent. So, always one root node in Tree (e.g. root node is ‘A’ in above Tree).
  • Degree – If A has 4 subtrees then it is called a degree of node A is 4. for example- the degree of A is 4, B-3, C-1, D-2, E-0, F-4, P-2)
  • Leaf or Terminal node- Leaf nodes are those nodes that have not child node. And the degree is must be 0. (e.g. Terminal/Leaf node: E, G, K, L, M, N, O, I, J, Q, R)

Parent & Child node – 

  • Parent node– The parent node in the tree is the Immediate Predecessor of a node is called a Parent node. (example- B, C, D, P->A, Where A is Parent node)
    Child node– Immediate successor of a node Is called the child node in Tree. (e.g. A->B, C, D, P Where B, C, D, P are the children of A)
    From the above statement child nodes B, C, D, P are the successor of A and A is the predecessor of B, C, D, P.
  • Sibling – As we see brother, sister in a family, children of the same parent same as in tree children node of the same parent node known as a sibling. (e.g. Q, R are the sibling child of P)
Siblings in a tree
  • Degree of Tree – maximum degree of a tree a1 any node in a tree is called a degree. (e.g. degree is 4 in the above tree diagram).
  • Ancestors -All the node along the path from the root node to that node. (e.g. L->A, B, F for enriching to the L node A, B, F are exist along the path it means these are the ancestors of L).
  • Descendants – All the nodes along the path from the node to terminal node (e.g. A->BFK, BFL, PQ, CHO).
  • Level of a node -If the node is at level I then its children is at(i+1) level.
  • Height or Depth of the tree-
    Depth -Root node depth is always 0 and the depth started from the root node counts the number of edges that come from the root of the tree. Therefore, in the above diagram A has 0 depth because no one edges come from the root node.
    Height -Count the maximum edge of a node from the root node.
How to find Height & depth of a tree
  • Forest – If we remove the root node from the tree, then it becomes a forest.
  • Binary Tree (BT) -It is a special tree. In which each node have almost two branches. In a binary tree maximum degree of any node is almost two.
 Binary tree

A Binary Tree has a finite set of nodes which can be either empty or consist of a root with two disjoint binary tree called left subtree & right subtree.

Example of Binary tree

Strictly Binary Tree -If every non-terminal node in a Binary Tree consists of a non-empty left subtree and right subtree, such a tree is called a strictly binary tree. (e.g. A,B,E)

Strictly Binary tree

Complete Binary Tree -A complete BT is a strictly BT in which all the terminal nodes leaves are at level I .

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top