Degree

Definition

The degree of a node in a tree is the number of its immediate children.

The degree of a tree is the maximum degree of any node in that tree.

If a node has:

0 children

• , its degree is 0

1 child

• , its degree is 1

2 children

• , its degree is 2
• and so on

The degree is always based on direct children only, not grandchildren or deeper descendants.

Main Content

1. First Concept

Degree of a Node

• : The degree of a node is the count of its immediate children. This is the most basic use of the term degree in trees. If a node branches into three child nodes, then its degree is 3. If it does not branch at all, its degree is 0.

Example

• : Consider the tree below:

          A
        / | \
       B  C  D
      / \
     E   F

Here:

• Node A has 3 children, so its degree is 3
• Node B has 2 children, so its degree is 2
• Nodes C, D, E, and F have no children, so each has degree 0

This concept is useful because it tells us how much a node contributes to branching in the tree.

2. Second Concept

Degree of a Tree

• : The degree of a tree is the largest degree among all its nodes. This means we check every node and find the node with the most children. That highest number becomes the degree of the tree.

Example

• : In the tree above, the degrees of the nodes are:
• A = 3
• B = 2
• C = 0
• D = 0
• E = 0
• F = 0

The highest degree is 3, so the degree of the tree is 3.

This is especially important when classifying trees:

• A binary tree has degree at most 2
• A ternary tree has degree at most 3
• A general tree may have any number of children at a node

3. Third Concept

Leaf Nodes and Internal Nodes

• : Degree helps distinguish between different types of nodes. A node with degree 0 is called a leaf node or external node because it has no children. A node with degree greater than 0 is called an internal node because it connects to other nodes below it.

Example

• :
• In the tree below:

          M
         / \
        N   O
           / \
          P   Q

• M has degree 2, so it is an internal node
• N has degree 0, so it is a leaf node
• O has degree 2, so it is an internal node
• P and Q have degree 0, so they are leaf nodes

Understanding degree helps in counting leaves, measuring branching, and analyzing tree structure in algorithms.

Working / Process

1. Identify a node in the tree

• Choose any node whose degree you want to find.
• Look only at the nodes directly connected below it.

2. Count the immediate children

• Count the number of child nodes attached directly to that node.
• Do not include grandchildren or deeper descendants.

3. Determine the tree’s degree if needed

• Find the degree of every node in the tree.
• The largest of these values is the degree of the tree.

Advantages / Applications

• Helps classify trees into binary, ternary, and general trees based on branching capacity.
• Useful in analyzing the structure of hierarchical data such as file systems, organization charts, and decision trees.
• Helps in designing and optimizing tree-based algorithms by showing how many links a node can have.

Summary

• Degree means the number of immediate children of a node.
• The degree of a tree is the highest degree of any node in the tree.
• Leaf nodes have degree 0.

Important terms to remember: node degree, tree degree, children, leaf node, internal node