ACompressed recap
🧾
A tree has one root, every other node has one parent, and there are no loops, so n nodes have n − 1 edges. Children, siblings, ancestors, descendants, leaves (no children), internal nodes and subtrees follow from the parent relation. Degree counts children. Depth counts edges up to the root, height counts edges down to the deepest leaf; in these notes the root is at level 0 and a single node has height 0, while the nodes convention adds 1 to everything.
BMerged rule card
4.1 Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention
- 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.
CInterleaved GATE-style questions
Q1NAT1 markEdges
A forest of 3 trees has 40 nodes in total. How many edges?
Numerical answer: ________
Q2MCQ1 markHeight
With the nodes convention, a tree whose longest root-to-leaf path has 6 edges has height:
- (A) 12
- (B) 5
- (C) 6
- (D) 7
Q3NAT2 marksLeaves
In a tree where every internal node has exactly 3 children and there are 10 internal nodes, how many leaves are there?
Numerical answer: ________
Q4MCQ1 markDepth
The depth of the root is (edges convention):
- (A) the height of the tree
- (B) 0
- (C) undefined
- (D) 1
Q5MSQ2 marksVocabulary
Which are always true in a tree?
- (A) Every node except the root has exactly one parent.
- (B) Every internal node has degree 2.
- (C) A leaf has height 0 (edges convention).
- (D) Siblings have the same depth.
Q6NAT1 markDegree
The node with the most children in a tree has 4 children. What is the degree of the tree?
Numerical answer: ________
Q7MCQ2 marksPossible?
Can a tree have 7 nodes and 7 edges?
- (A) No: it would contain a loop
- (B) Only if every node is a leaf
- (C) Only if it is a forest
- (D) Yes
Q8MCQ1 markAncestors
In the company chart of Lesson 4.1, how many ancestors does Intern have?
- (A) 1
- (B) 4
- (C) 3
- (D) 2
DAnswer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 371 mark
Each tree has nodes − 1 edges: 40 − 3 = 37.
Re-read: Lesson 4.1 — Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention
Q2 Answer: (D)1 mark
6 edges = 7 nodes.
- (A) is wrong: Not doubled.
- (B) is wrong: Too small.
- (C) is wrong: That is the edges convention.
Re-read: Lesson 4.1 — Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention
Q3 Answer: 212 marks
Edges = 30, nodes = 31, leaves = 31 − 10 = 21.
Re-read: Lesson 4.1 — Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention
Q4 Answer: (B)1 mark
No edges above it.
- (A) is wrong: Height is measured downwards.
- (C) is wrong: It is 0.
- (D) is wrong: That is the nodes convention.
Re-read: Lesson 4.1 — Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention
Q5 Answer: (A) (C) (D)2 marks
Degrees can be anything ≥ 1.
- (B) is wrong: Internal nodes can have any number of children.
Re-read: Lesson 4.1 — Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention
Q6 Answer: 41 mark
4.
Re-read: Lesson 4.1 — Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention
Q7 Answer: (A)2 marks
n nodes → n − 1 edges; one extra edge closes a loop.
- (B) is wrong: Leaves only means one node.
- (C) is wrong: A forest has fewer edges, not more.
- (D) is wrong: Contradicts n − 1 edges.
Re-read: Lesson 4.1 — Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention
Q8 Answer: (C)1 mark
Ops3, COO, CEO.
- (A) is wrong: More than its parent.
- (B) is wrong: Intern is not its own ancestor.
- (D) is wrong: CEO is an ancestor too.
Re-read: Lesson 4.1 — Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention