Tree in data structure tutorial is very important concept in data structure.
In this tutorial we are going to see tree in data structure, tree in data structure definition, and tree terminology.
What is tree in data structure ?
Tree in data structure definition : Tree is finite set of nodes with one specially designed node called root and remaining nodes are partitioned into n >= 0 disjoint sets T1 to Tn where each of those set is tree.
T1 to Tn is called as subtree of root.
In this example A,B,C,D,E,F,G,H are nodes and A is a special node called root.
Node : It is an item of information along with edges called as node.
In above example there are 8 nodes.
Leaf node : Leaf node is a terminal of a tree, it does not have any node connected to it.
In above example F,H, G,D are the leaf nodes and remaining nodes are called as non leaf node.
Degree of node : The number of sub tree of the node is called as degree of node.
Example degree of A = 3
Degree of B = 2
Degree of tree : Is the maximum number of nodes.
Example Degree of tree = 3
Parent node : Is a node having other node connected to it. All that connected nodes are called as child node of that node.
A is a parent node of B, C, D
C is a parent node of G
Sibling : Children of the same parent are called as siblings
Example B,C,D are siblings
Descendants : Descendants of the nodes are all those nodes which are reachable from that node.
Example descendants of B is E,F, H
Ancestors : Ancestors of the node are all the nodes along the path from the root to that node.
Example ancestors of E is B and A
Levels of node : This indicate the position of node in hierarchy
Formula level of any node = level of its parents + 1
The level of root is always zero
Level of D = 1
Height or depth of tree : The maximum level of any node is called as depth or height of tree .
Example height of above tree is 3
Forest : It is a set of n >= 0 disjoint trees that is if we remove the root we gets the forest trees.
If we remove node A from above trre then it makes following disjoint trees which are called as forest.
Tree types data structure
Ternary tree : Every node has less than or equal to 3 nodes.
Binary tree : Binary tree in which every node has less than or equal to 2 children.
Complete binary tree : Tree in which every node has 0 or 2 children
Binary search tree :
In Binary search tree every node has following property
All nodes in left sub tree have value less than or equal to parent node
and nodes in right sub tree have value greater than or equal to parent node