12. Tree and its terminologies

 

Tree

• Tree is a non-linear advanced data structure and represents a hierarchical relationship existing between several data items.
• A tree may be defined as a finite set T of one or more nodes that are connected by edges.
• The topmost node of the tree is called the root, and the nodes below it are called the child nodes.
• Each node can have multiple child nodes and these child nodes can also have their own child nodes, forming a recursive structure.

Root

• The first/top node is called root node.
• We always have exactly one root node in every tree.
• We can say that root node is the origin of tree data structure.

Edge

• In a tree data structure, the connecting link between any two nodes is called as Edge.
• In a tree with N number of nodes, there will be exactly of N-1 number of edges.

Parent

• In a tree data structure, the node which is predecessor of any node is called as parent node.
• Here, A is the parent of B and C. B is the parent of D, E and F. C is the parent of G and H. E is the parent of I and J. G is the parent of K.

Child

• In a tree data structure, the node which is descendant of any node is called as child node.
• Here, B and C are childrens of A. D, E and F are childrens of B. G and H are childrens of C. I and J are childrens of R. K is children of G.

Siblings

• Children of the same parent node are called siblings.
• Here, B and C are siblings. Here, D, E and F are siblings.

Leaf / External / Terminal

• In a tree data structure, the node which does not have a child is called as leaf node.
• Here, D, F, H, I, J and K are leaf nodes.

Internal / Non-Terminal

• The node which has at least one child is called as internal node.
• Nodes other than leaf nodes are called as internal nodes.
• Here, A, B, C, E, G are internal nodes.

Degree

• The total number of children of a node is called as degree of node.
• The highest degree allowed of a node in a tree is called as "Degree of Tree".
• Here, degree of B is 3, degree of A is 2, degree of C is 2, degree of E is 2, degree of G is 1 and degree of all leaf nodes is 0. Hence degree of tree is 3.

Level / Depth / Height

• Each step from top to bottom is called as a Level and the level count starts with 0 and incremented by one at each level.
• The depth of a node is the number of edges present in path from the root node of a tree to that node.
• The height of a node is the number of edges present in the longest path connecting that node to a leaf node.

Path

• The sequence of nodes and edges from one node to another node is called as path between that two nodes.
• Length of path is total number of nodes in that path.
• Here, path between A and I is: A-B-E-I. Path between C and K is: C-G-K.

Ancestor

• Any predecessor nodes on the path of the root to that node are called ancestors of that node.
• Here, ancestors of I are E, B and A. Ancestors of C is A only.

Descendant

• Any successor node on the path from the leaf node to that node.
• Here, B is the descendant of A.

Subtree

• Each child from a node forms a subtree recursively.
• Every child node will form a subtree on its parent node.