The GATE Grind

GATE 2012 CS (CS1) – Question 57

Programming and Data Structures · Trees and Binary Search Trees · 2 marks · Multiple choice

Height counts edges on the longest downward path. Fill B1 and B2.

int height(treeptr n) {
    if (n == NULL) return -1;
    if (n->left == NULL)
        if (n->right == NULL) return 0;
        else return B1;
    else {
        h1=height(n->left);
        if (n->right == NULL) return 1+h1;
        else { h2=height(n->right); return B2; }
    }
}
  1. B1=1+height(n->right); B2=1+max(h1,h2)
  2. B1=height(n->right); B2=1+max(h1,h2)
  3. B1=height(n->right); B2=max(h1,h2)
  4. B1=1+height(n->right); B2=max(h1,h2)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) B1=1+height(n->right); B2=1+max(h1,h2)

Explanation

If only the right child exists, count its subtree height plus the edge to it, giving B1=1+height(right). With both children present, the longer child subtree determines height, again plus one edge: B2=1+max(h1,h2). Thus A.

More Trees and Binary Search Trees questions

All Trees and Binary Search Trees questions →