Skip to content
GATETECH
Official PYQ · 2004Q43TreesMCQ1 mark

GATE CS 2004 Q43 — Trees

Explain with AI

Consider the following C program segment

struct CellNode{
    struct CellNode *leftChild
    int element;
    struct CellNode *rightChild;
    };

int Dosomething (struct CellNode *ptr)
{
    int value = 0;
    if(ptr != NULL)
    { 
        if (ptr -> leftChild != NULL)
            value = 1 + DoSomething (ptr -> leftChild);
        if (ptr -> rightChild != NULL)
            value = max(value, 1 + Dosomething (ptr -> rightChild));
    }
    return(value);
}

The value returned by the function DoSomething\text{DoSomething} when a pointer to the root of a non-empty tree is passed as argument is

Choose one option
View worked solution

Answer: D

Let us analyze the behavior of the function DoSomething(ptr) by tracing it on simple binary trees:

  1. Single-node tree (Root only):

    Since both leftChild and rightChild are NULL, the conditions inside the if blocks are false. The function returns the initial value, which is 0.

  2. Two-node tree (Root with one child):

    For the root, the child is not NULL. The function recursively calls itself on the child (which returns 0) and sets value = 1 + 0 = 1. It returns 1.

  3. Three-node tree (Root with left and right children):

    The left recursive call returns 0, setting value = 1 + 0 = 1. The right recursive call also returns 0, and the function updates value = max(1, 1 + 0) = 1. It returns 1.

In general, for any node, the function computes 1+max⁡(height of left subtree,height of right subtree)1 + \max(\text{height of left subtree}, \text{height of right subtree}). This is the standard recursive definition for the height of the tree (measured as the number of edges on the longest path from the root to a leaf).

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Trees questions