Binary Trees – Data Structures and Algorithms:
Exam-Ready Questions and Answers
LATEST UPDATE 2026/2027 | PREMIUM ACADEMIC EDITION
Exam 17 of 40 | Unit code: DSA-17 | Questions: 6 | Total marks: 30 | Answer ALL questions
Question 1: [5 marks]
Define a binary tree and the terms root, leaf, depth, height and level.
Answer:
A binary tree is a hierarchical structure in which each node has at most two children (left and
right).
• Root: the topmost node. Leaf: a node with no children.
• Depth of a node: the number of edges from the root to it.
• Height of a node: the number of edges on the longest path down to a leaf.
• Level: all nodes at the same depth.
Question 2: [5 marks]
State the maximum number of nodes at level l and in a binary tree of height h (root at level 0).
Answer:
At level l: at most 2l nodes. In a tree of height h: at most 1 + 2 + 4 + … + 2h = 2h+1 − 1 nodes.
Question 3: [5 marks]
Distinguish between full, complete and perfect binary trees.
Answer:
• Full: every node has 0 or 2 children.
• Complete: all levels are completely filled except possibly the last, which is filled from left to
right.
• Perfect: all internal nodes have two children and all leaves are at the same level.
Question 4: [4 marks]
How many nodes and how many leaves does a perfect binary tree of height 4 have?
Answer:
4+1 4
Nodes: 2 − 1 = 31. Leaves (level 4): 2 = 16.
Question 5: [5 marks]
Write a recursive function that returns the height of a binary tree. State its complexity.
Page 1 Data Structures and Algorithms • Exam 17
Exam-Ready Questions and Answers
LATEST UPDATE 2026/2027 | PREMIUM ACADEMIC EDITION
Exam 17 of 40 | Unit code: DSA-17 | Questions: 6 | Total marks: 30 | Answer ALL questions
Question 1: [5 marks]
Define a binary tree and the terms root, leaf, depth, height and level.
Answer:
A binary tree is a hierarchical structure in which each node has at most two children (left and
right).
• Root: the topmost node. Leaf: a node with no children.
• Depth of a node: the number of edges from the root to it.
• Height of a node: the number of edges on the longest path down to a leaf.
• Level: all nodes at the same depth.
Question 2: [5 marks]
State the maximum number of nodes at level l and in a binary tree of height h (root at level 0).
Answer:
At level l: at most 2l nodes. In a tree of height h: at most 1 + 2 + 4 + … + 2h = 2h+1 − 1 nodes.
Question 3: [5 marks]
Distinguish between full, complete and perfect binary trees.
Answer:
• Full: every node has 0 or 2 children.
• Complete: all levels are completely filled except possibly the last, which is filled from left to
right.
• Perfect: all internal nodes have two children and all leaves are at the same level.
Question 4: [4 marks]
How many nodes and how many leaves does a perfect binary tree of height 4 have?
Answer:
4+1 4
Nodes: 2 − 1 = 31. Leaves (level 4): 2 = 16.
Question 5: [5 marks]
Write a recursive function that returns the height of a binary tree. State its complexity.
Page 1 Data Structures and Algorithms • Exam 17