Question Details

Consider a heap containing n elements, where n > 100 and n is odd. Assuming 1-based indexing, which of the following cannot be the index of a leaf node in the heap?

Options

A

(n−1)/2

B

(n−3)/2

C

n

D

(n+1)/2

Show Answer
Correct Answer
A (n−1)/2

Solution :

The correct answer is (n−1)/2.

To understand why this is correct, let us analyze the properties of a binary heap represented as an array with 1-based indexing. For any node at index i in a heap containing n elements:
- The left child of the node is located at index 2i.
- The right child of the node is located at index 2i+1.
- A node is a leaf node if it has no children, which means its left child index exceeds the total number of elements in the heap: 2i>n.
- Conversely, a node is an internal (non-leaf) node if it has at least one child, which means:

2i≤n

Let us now test the index given in the correct option, which is:

i=n-12

To determine if this node can be a leaf, we calculate the index of its left child:

Left Child Index=2i=2n-12=n-1

Since we are given that n>100, it is clear that:

n-1≤n

This means the index of the left child, n-1, is a valid position within the heap. In fact, since n is odd, the node at index n-12 also has a right child at index n. Because the node at index n-12 has children, it must be an internal node and cannot be a leaf node in the heap.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: