Exams › GATE › Technical

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root. ```c 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; } } } ``` The appropriate expressions for the two boxes B1 and B2 are

1. B1: $(1 + \text{height}(n->right))$; B2: $(1 + \max(h1, h2))$
2. B1: $\text{height}(n->right)$; B2: $(1 + \max(h1, h2))$
3. B1: $\text{height}(n->right)$; B2: $\max(h1, h2)$
4. B1: $(1 + \text{height}(n->right))$; B2: $\max(h1, h2)$

Correct answer: B1: $(1 + \text{height}(n->right))$; B2: $(1 + \max(h1, h2))$

Solution

A null node has height -1, so a leaf node has height 0. If only the right child exists, the height is 1 plus the height of the right subtree; if both children exist, the height is 1 plus the maximum of the left and right subtree heights.

Related GATE Technical questions

• A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
• An array \([82, 101, 90, 11, 111, 75, 33, 131, 44, 93]\) is heapified. Which one of the following options represents the first three elements in the heapified array?
• Consider a binary min-heap containing 105 distinct elements. Let \(k\) be the index in the underlying array of the maximum element stored in the heap. The number of possible values of \(k\) is
• Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
• The height of a binary tree is the maximum number of edges in any root-to-leaf path. The maximum number of nodes in a binary tree of height $h$ is:
• The maximum number of binary trees that can be formed with three unlabeled nodes is:

⚔️ Practice GATE Technical free + battle 1v1 →