A tree is a hierarchical data structure defined as a collection of nodes. Nodes represent value and nodes are connected by edges. A tree has the following properties:
The tree has one node called root. The tree originates from this, and hence it does not have any parent.
Each node has one parent only but can have multiple children.
Each node is connected to its children via edge.
Following diagram explains various terminologies used in a tree structure.
Also Read: Introduction to Decision Trees
Terminology Description Example From Diagram
Root Root is a special node in a tree. The entire tree originates from it. It does not have a parent. Node A
Parent Node Parent node is an immediate predecessor of a node. B is parent of D & E
Child Node All immediate successors of a node are its children. D & E are children of B
Leaf Node which does not have any child is called as leaf H, I, J, F and G are leaf nodes
Edge Edge is a connection between one node to another. It is a line between two nodes or a node and a leaf. Line between A & B is edge
Siblings Nodes with the same parent are called Siblings. D & E are siblings
Path / Traversing Path is a number of successive edges from source node to destination node. A – B – E – J is path from node A to E
Height of Node Height of a node represents the number of edges on the longest path between that node and a leaf. A, B, C, D & E can have height. Height of A is no. of edges between A and H, as that is the longest path, which is 3. Height of C is 1
Levels of node 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 Level of H, I & J is 3. Level of D, E, F & G is 2
Degree of Node Degree of a node represents the number of children of a node. Degree of D is 2 and of E is 1
Sub tree Descendants of a node represent subtree.
