GATE CSE 2022 Q28: Array index of the 3rd largest element of a complete BST

Programming and Data Structures
1 mark
NAT
No negative marking

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index_____________.

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 509 (official GATE 2022 final answer key)

Concept used: In 0-indexed heap layout, node $i$ has children $2i+1$ and $2i+2$ ; the largest BST elements lie at the end of the rightmost path.

First step: Follow right children from the root: $0, 2, 6, 14, \ldots$ until the next index would exceed 999.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2022 questions →

GATE CSE 2022 Q28: Array index of the 3rd largest element of a complete BST

Question

Full step-by-step solution

More Programming and Data Structures PYQs