Last Updated: 18 January, 2025 6 Mins Read
A Tree is a hierarchical data structure that consists of nodes connected by edges. Each node contains a value (data) and may have zero or more child nodes. The topmost node in a tree is called the root node, and the nodes at the bottom that do not have children are called leaf nodes.
Node: In a tree, Node is an object or entity that contains data and reference (address) to its all child nodes.
For example, In the given tree, there are total 6 Nodes (A, B, C, D, E, F).
Edge: In a tree, Edge makes a connection or link between two nodes. In a tree with 'N' nodes will have a maximum of 'N-1' edges.
For example, in the given tree below, the line connecting Nodes A and B is called an edge.
Root Node: The first node or top most node is a called a Root node, it does have a parent node and it will be a only one in a tree.
In the given tree, A is the root node.
Parent Node: A node that is a node's predecessor is called a Parent node in a tree. A parent node contains the referece (address) of its child nodes.
For better understanding, lets see the tree below.
Child Node: The descendant node of any node is called a child node in a tree.
For example, In the given tree, A is the root node, and B and C are child nodes of A; similarly, D and E are child nodes of B, and F is a child node of C.
Sibling: In general as we know that children of the same parent are called siblings. There is a sample meaning in the tree also, two child nodes connected to a same parent node is called as sibling.
For example, In the given tree below:
Leaf Node: A node that has no child nodes is known as a leaf node. A leaf node is the tree's lowest node. Leaf nodes are also known as exterior nodes.
For example, we can see in the below tree here D, G, I, J, H are the leaf node.
Degree of a Node: The degree of a node means the total number of its children. A node with the highest degree in a tree is referred to as a degree of tree.
For example, In the given tree below, nodes degree are as follow:
Nodes D, F, I, J, G, H degree is 0 as they don't have child.
In tree, all the leave nodes degree is 0.
Height of a node: The height of a node is the total number of edges that connect a leaf node to a specific node along the longest path.
In a tree, height of all leaf nodes will be always '0'.
For better understanding, lets see the tree below.
Depth of a node: In a tree, the total number of edges from the root node to a specific node is known as the depth of that node.
In a tree, depth of root node will be always '0'.
For better understanding, lets see the tree below.
Path: In a tree, the path between two nodes is the sequence of nodes and edges that connects them. The total number of nodes in a path defines its length.
For better understanding, lets see the tree below.
Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node.
For example, In the given tree, Nodes A and B are the ancestor nodes of node {E}.
Descendant: A node x is a descendant of another node y if and only if y is an ancestor of x.
For example, node H is descendant of node C as given in the below tree.
Level of a node: Each step from top to bottom is referred to as a level in a tree. Always a root node level is 0, the next child node is at level 1, the grandchild at level 2, and so on.
Internal node: A node that has one or more child nodes is called an internal node; it is also known as Non-Terminal nodes.
A leaf node will never be an internal node in a tree.
For example, In the given tree below, nodes A, B, C, E, G are Internal Nodes and remaining are leaf nodes.
Neighbour of a Node: The parent or child nodes of that node are referred to as neighbors.
For better understanding, lets see the tree below.
Subtree: In a tree, A subtree will be formed on every single parent node by each child node.
For better understanding, lets see the tree below.
That's all, guys. I hope this article is helpful for you.
Happy Learning... 😀
Please share this article on social media to help others.
feedback@javabytechie.com