![GATE 2014 [Set-3]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
GATE 2014 [Set-3]
April 3, 2025GATE 2014 [Set-2]
April 3, 2025GATE 2014 [Set-3]
| Question 51 |
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
int value=0;
if (tree != NULL)
{
if (tree->leftMostChild == NULL)
value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
| number of internal nodes in the tree. | |
| height of the tree. | |
| number of nodes without a right sibling in the tree. | |
| number of leaf nodes in the tree. |
Question 51 Explanation:
The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time.
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the sub-tree or the current node as called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered.
⇒ The function returns the number of leaf nodes in the tree.
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the sub-tree or the current node as called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered.
⇒ The function returns the number of leaf nodes in the tree.
Correct Answer: D
Question 51 Explanation:
The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time.
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the sub-tree or the current node as called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered.
⇒ The function returns the number of leaf nodes in the tree.
Here, that condition is if (tree → leftMostchild = = Null)
⇒ Which means if there is no left most child of the tree (or the sub-tree or the current node as called in recursion)
⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
⇒ Which means the node under consideration is a leaf node.
⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered.
⇒ The function returns the number of leaf nodes in the tree.