CS Atlas GATE 2027
PDS course
0 / 103 complete

PDS/Phase 4 · Trees & Binary Search Trees

Checkpoint CP4 · Item 80 of 103

Trees & binary search trees

Read at your own pace. Try the questions before opening the answers.

On this page

⏱️

15 questions · 24 marks · 50 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.

Q1NAT1 markVocabulary

A tree has 60 nodes. How many edges?

Numerical answer: ________

Q2NAT2 marksn₀ = n₂ + 1

A binary tree has 17 leaves and 9 nodes with exactly one child. How many nodes in total?

Numerical answer: ________

Q3NAT1 markHeight

Minimum height (edges) of a binary tree with 500 nodes?

Numerical answer: ________

Q4NAT1 markIndexing

In a 1-based array heap-style layout, the parent of index 21 is:

Numerical answer: ________

Q5MCQ2 marksTraversal

The tree of Lesson 4.3.1 Example 1 has postorder:

  • (A) A B D E G H C F I
  • (B) D B G E H A C I F
  • (C) D G H E B I F C A
  • (D) D G H E B F I C A

Q6MCQ2 marksRebuild

Preorder 10 5 1 7 40 50 and inorder 1 5 7 10 40 50. The postorder is:

  • (A) 1 5 7 40 50 10
  • (B) 1 7 5 50 40 10
  • (C) 1 7 5 40 50 10
  • (D) 7 1 5 50 40 10

Q7NAT1 markCatalan

How many binary tree shapes have 5 nodes?

Numerical answer: ________

Q8NAT2 marksRecursion

What does this print?

int h(struct tnode *t, int d)
{
    if (t == NULL) return 0;
    if (t->left == NULL && t->right == NULL) return d;
    return h(t->left, d + 1) + h(t->right, d + 1);
}

int main(void)
{
    struct tnode *root = mk(1, mk(2, mk(4, NULL, NULL), mk(5, mk(7, NULL, NULL), NULL)), mk(3, NULL, mk(6, NULL, NULL)));
    printf("%d\n", h(root, 0));
    return 0;
}

Numerical answer: ________

Q9MCQ1 markExpression

The prefix form produced by preorder of the tree for (a − b) * (c + d) is:

  • (A) * - a b + c d
  • (B) * a - b + c d
  • (C) a b - c d + *
  • (D) - * a b + c d

Q10NAT2 marksBST height

Keys 40, 20, 60, 10, 30, 50, 70, 35, 33 are inserted into an empty BST. Height (edges)?

Numerical answer: ________

Q11MCQ2 marksDelete

From the BST of the previous question, 20 is deleted using the inorder successor. Which key replaces 20?

  • (A) 30
  • (B) 35
  • (C) 33
  • (D) 10

Q12MCQ2 marksSearch path

Which is a valid BST search path for 35?

  • (A) 50 60 30 35
  • (B) 10 50 20 60 35
  • (C) 50 20 40 45 35
  • (D) 50 20 40 30 35

Q13NAT2 marksInsertion orders

How many insertion orders of {1, 2, 3, 4, 5, 6, 7} produce the BST whose preorder is 4 2 1 3 6 5 7?

Numerical answer: ________

Q14NAT1 markAVL

Minimum nodes of an AVL tree of height 4 (edges)?

Numerical answer: ________

Q15MSQ2 marksMixed

Which are true?

  • (A) Inorder of a BST is sorted.
  • (B) Level order uses a queue.
  • (C) Preorder + postorder always determines a binary tree.
  • (D) An AVL insertion needs at most one single or double rotation.

Answer Vault

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

Q1 Answer: 591 mark

n − 1.

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: 422 marks

n₂ = 16; 17 + 9 + 16 = 42.

Re-read: Lesson 4.2.2 — Binary tree properties: nodes per level and height; n₀ = n₂ + 1; minimum and maximum height

Q3 Answer: 81 mark

⌊log₂ 500⌋ = 8.

Re-read: Lesson 4.2.2 — Binary tree properties: nodes per level and height; n₀ = n₂ + 1; minimum and maximum height

Q4 Answer: 101 mark

⌊21/2⌋ = 10.

Re-read: Lesson 4.2.3 — Representations: linked nodes vs array indexing (both 0-based and 1-based formulas)

Q5 Answer: (C)2 marks

Left, right, root.

  • (A) is wrong: Preorder.
  • (B) is wrong: Inorder.
  • (D) is wrong: I is F’s left child: I before F.

Re-read: Lesson 4.3.1 — Preorder, inorder, postorder (recursive code and hand tracing)

Q6 Answer: (B)2 marks

1 7 5 50 40 10.

  • (A) is wrong: That is not a postorder of this tree.
  • (C) is wrong: 50 is under 40: 50 before 40.
  • (D) is wrong: 1 is the left child, before 7.

Re-read: Lesson 4.3.3 — Rebuilding a tree from two traversals; counting distinct binary trees (Catalan)

Q7 Answer: 421 mark

C(5).

Re-read: Lesson 4.3.3 — Rebuilding a tree from two traversals; counting distinct binary trees (Catalan)

Q8 Answer: 72 marks

Sum of leaf depths.

Output

7

Re-read: Lesson 4.4 — Recursive code on trees: count nodes, leaves, height, mirror, sums; expression trees

Q9 Answer: (A)1 mark

Root * first, then each subtree in preorder.

  • (B) is wrong: − applies to a and b.
  • (C) is wrong: That is postorder.
  • (D) is wrong: The root is *.

Re-read: Lesson 4.4 — Recursive code on trees: count nodes, leaves, height, mirror, sums; expression trees

Q10 Answer: 42 marks

40 → 20 → 30 → 35 → 33: 4.

Re-read: Lesson 4.5.2 — BST insertion; building a BST from an insertion sequence; best- vs worst-case height

Q11 Answer: (A)2 marks

Minimum of 20’s right subtree {30, 35, 33} is 30.

  • (B) is wrong: 35 is larger than 30.
  • (C) is wrong: 33 is larger than 30.
  • (D) is wrong: 10 is the predecessor.

Re-read: Lesson 4.5.3 — BST deletion: leaf, one child, two children (inorder successor or predecessor)

Q12 Answer: (D)2 marks

true,false,false,false.

  • (A) is wrong: 60 then 30 violates the lower bound 50.
  • (B) is wrong: 60 exceeds the bound 50.
  • (C) is wrong: 45 exceeds the bound 40.

Re-read: Lesson 4.5.4 — BST GATE drills: BST from a preorder/postorder sequence; number of BSTs; valid search paths; insertion orders giving the same BST

Q13 Answer: 802 marks

C(6, 3) × 2 × 2 = 80.

Re-read: Lesson 4.5.4 — BST GATE drills: BST from a preorder/postorder sequence; number of BSTs; valid search paths; insertion orders giving the same BST

Q14 Answer: 121 mark

N(4) = 7 + 4 + 1 = 12.

Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height

Q15 Answer: (A) (B) (D)2 marks

Pre + post is ambiguous for single children.

  • (C) is wrong: Only for strict trees.

Re-read: Lesson 4.3.3 — Rebuilding a tree from two traversals; counting distinct binary trees (Catalan)

If you got these wrong, re-read

QuestionMarksTopicRe-read
Q11VocabularyLesson 4.1
Q22n₀ = n₂ + 1Lesson 4.2.2
Q31HeightLesson 4.2.2
Q41IndexingLesson 4.2.3
Q52TraversalLesson 4.3.1
Q62RebuildLesson 4.3.3
Q71CatalanLesson 4.3.3
Q82RecursionLesson 4.4
Q91ExpressionLesson 4.4
Q102BST heightLesson 4.5.2
Q112DeleteLesson 4.5.3
Q122Search pathLesson 4.5.4
Q132Insertion ordersLesson 4.5.4
Q141AVLLesson 4.6
Q152MixedLesson 4.3.3
ONE MORE CONNECTION MADE

Ready for the next idea?

Mark this item complete when you’ve finished reading and working through it.