4.1 Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention · GATE 2027 Programming and Data Structures

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

What does p->next = p->next->next do? from Lesson 3.4.5
How many pointers change when inserting into the middle of a doubly linked list? from Lesson 3.4.3
In a recursion tree, what does each box stand for, and what are the boxes at the bottom? from Lesson 2.1.2

1 · The Hook

🎣

A company chart has a CEO at the top, managers below, and staff below them. Folders on a computer contain folders that contain files. A family tree branches from one ancestor. None of these is a line: each item can have several items below it, but exactly one above it. Lists cannot represent this shape naturally; trees can.

2 · Predict First

🤔

In the company chart drawn below (11 people, everyone except the CEO has exactly one boss), how many boss–employee links are there? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

10. Every person except the top one has exactly one link going up, so a tree with n nodes always has n − 1 edges.

What a tree is

A tree is a set of nodes connected by edges such that one node, the root, has no node above it, and every other node has exactly one node directly above it. There are no loops. A tree with n nodes has n − 1 edges.

Family words

The node directly above x is x’s parent; the nodes directly below x are its children; children of the same parent are siblings.
Nodes above x on the way to the root are its ancestors; nodes below it are its descendants.
A node with no children is a leaf (external node); a node with at least one child is an internal node.
A node together with all its descendants forms a subtree.
Several separate trees form a forest.

Degree

The degree of a node is its number of children. The degree of the tree is the largest degree of any node. Leaves have degree 0.

Level, depth and height

The depth of a node is the number of edges on the path from the root to it. The root has depth 0.
The level of a node: in these notes level = depth, so the root is at level 0.
The height of a node is the number of edges on the longest path from it down to a leaf. A leaf has height 0.
The height of the tree is the height of its root (= the largest depth). An empty tree has height −1 in this convention.

The edges-vs-nodes convention (read every question!)

Textbooks disagree: some count height and depth in nodes (a single node has height 1, the root is at level 1). Counting in nodes simply adds 1 to every height and level. GATE questions usually say which convention they use (“height of a single node is 0”, “root at level 1”). When they do not, the edge convention is the more common one. Always restate the convention before computing.

Quantity	Edges convention (these notes)	Nodes convention
single node: height	0	1
root: level / depth	0	1
empty tree: height	−1	0
example chart below: height	3	4

4 · Visual

Diagram: Dev1 · Dev2 · CTO · Acct · CFO · Ops1 · Ops2 · Intern · Ops3 · COO · CEO

A tree of 11 nodes and 10 edges. Root: CEO. Leaves (green): 6. Degree of COO: 3 (also the degree of the tree). Height: 3 (CEO → COO → Ops3 → Intern).

CEO                level 0   depth 0
           /          |          \
         CTO         CFO         COO         level 1
        /   \         |       /   |   \
     Dev1   Dev2    Acct   Ops1  Ops2  Ops3  level 2
                                         |
                                       Intern level 3

 parent(Ops3) = COO      children(COO) = Ops1, Ops2, Ops3      siblings of CFO: CTO, COO
 ancestors(Intern) = Ops3, COO, CEO     leaves: Dev1 Dev2 Acct Ops1 Ops2 Intern
 height(COO) = 2   depth(COO) = 1   height of tree = 3 (edges)

Every vocabulary word, read off one picture.

5 · Worked Examples

Example 1 Easy

In the chart above, name the parent of Acct, the siblings of Dev1, and the degree of CTO.

Solution

Parent of Acct: CFO. Siblings of Dev1: Dev2. Degree of CTO: 2.

Example 2 Medium

For the chart, give the number of leaves, internal nodes, the height of CTO and the depth of Intern.

Solution

Leaves: 6; internal: 5 (CEO, CTO, CFO, COO); height of CTO: 1; depth of Intern: 3.

Example 3 GATE

A tree has 12 nodes. Of these, 4 have degree 3, 2 have degree 1 and the rest are leaves. Is that possible? (Use the edge count.)

Solution

Edges = sum of degrees = 4·3 + 2·1 = 14, but a tree with 12 nodes has 11 edges. Impossible. (With 4 nodes of degree 3 and 2 of degree 1, the tree has 15 edges and so 16 nodes, 10 of them leaves.)

6 · GATE Traps

⚠️

Height and depth may be counted in edges or in nodes; they differ by exactly 1. Use the question’s convention.
The height of a node is measured downwards (to a leaf), the depth upwards (to the root).
Degree counts children only, not the parent.
A tree with n nodes has exactly n − 1 edges.
The root is an ancestor of every other node; a node is not its own ancestor.

8 · Memory Hook

🧠

“Depth looks up, height looks down.” Depth = edges from the root above; height = edges to the farthest leaf below. Every node has one parent, so edges = nodes − 1.

9 · Connect the Dots

Recursion trees (Lesson 2.1.2) were trees already; now the vocabulary is formal. Most data-structure trees limit each node to at most two children, which makes them easy to store and to search. Next lesson answers: what kinds of trees with at most two children are there, and how do they differ?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markEdges

How many edges does a tree with 25 nodes have?

Numerical answer: ________

Q2MCQ1 markConvention

A tree is a single path of 5 nodes. Its height in the edges convention and in the nodes convention is:

(A) 4 and 5
(B) 4 and 4
(C) 5 and 4
(D) 5 and 5

Q3MCQ1 markVocabulary

A node with no children is called:

(A) a root
(B) an internal node
(C) a sibling
(D) a leaf

Q4NAT2 marksDegrees

A tree has 3 nodes of degree 2, 2 nodes of degree 3, and all other nodes are leaves. How many leaves does it have?

Numerical answer: ________

Q5MSQ1 markFacts

In the company chart of this lesson, which are true?

(A) COO is an ancestor of Intern
(B) The depth of Ops2 is 2
(C) Dev1 and Acct are siblings
(D) CEO has height 3

11 · Rule Card

Tree: one root, every other node has exactly one parent, no loops; n nodes → n − 1 edges.
parent/child/sibling; ancestor/descendant; leaf (no children) vs internal; subtree; forest.
Degree of node = number of children; degree of tree = maximum.
Depth = edges from root; level = depth (root 0 here); height = edges to the deepest leaf; empty tree −1.
Nodes convention adds 1 to every height/level: always state it.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

treerootparentchildsiblingancestordescendantleafinternal nodesubtreeforestdegreeedgeleveldepthheightedges vs nodes convention

13 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

Unlinks the node after p from the list.
Each box is one call; the bottom boxes are base cases.