The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 votes

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));

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

  1. The number of leaf nodes in the tree
  2. The number of nodes in the tree
  3. The number of internal nodes in the tree
  4. The height of the tree
asked in DS by Veteran (59.6k points) | 1.2k views

1st if calculates the height of the left subtree and 2nd if computes the height of the right subtree and takes the max of (height of left subtree, height of right subtree).

as program is comparing values from left and right sub tree , hence result can not be count of leaf , internal nodes , total nodes hence option a,b,c can be  eliminated

2 Answers

+22 votes
Best answer

(D) It calculates Height of tree.

Easy way to get this answer .

Draw a tree where all $4$ parameters are different.

Get a Tree for which Height, No of Internal Nodes & No of Leafs are different & Trace out this algorithm.

answered by Boss (42.9k points)
edited by

The below diagram may make the code easier to understand.

+3 votes
It actually calculates the height of the tree

How I did that: I drew a tree then just tried the algo on this tree and then I modified the tree wisely,  then I tried the algo one more time
answered by Boss (14.3k points)
Wow ... Thug life (y) ...

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,748 questions
47,471 answers
62,234 users