What does the following function do for a given binary tree?int fun(st...
The function counts internal nodes. 1) If root is NULL or a leaf node, it returns 0. 2) Otherwise returns, 1 plus count of internal nodes in left subtree, plus count of internal nodes in right subtree.
View all questions of this test
What does the following function do for a given binary tree?int fun(st...
Explanation:
The given function is designed to count the number of internal nodes in a binary tree. Let's break down the code step by step to understand how it works.
1. Base Case:
- The first condition checks if the root is NULL. If it is, it means the tree is empty and there are no nodes to count, so the function returns 0.
2. Leaf Node Case:
- The second condition checks if both the left and right children of the root are NULL. If both are NULL, it means the root is a leaf node and has no children. Leaf nodes are not considered internal nodes, so the function returns 0.
3. Recursive Calls:
- If the above two conditions are not met, it means the root is an internal node with at least one child. In this case, the function makes recursive calls to count the internal nodes in the left and right subtrees.
- The number of internal nodes in the left subtree is calculated by calling the function with the left child of the root: `fun(root->left)`.
- The number of internal nodes in the right subtree is calculated by calling the function with the right child of the root: `fun(root->right)`.
4. Return Statement:
- After the recursive calls, the function returns 1. This 1 represents the root node itself, which is an internal node.
Example:
Let's consider a binary tree with the following structure:
```
1
/ \
2 3
/ \
4 5
```
- When the function is called with the root of this tree, it will first check if the root is NULL or a leaf node. Since neither of these conditions is true, it will make recursive calls to count the internal nodes in the left and right subtrees.
- The left subtree has two internal nodes (2 and 4), and the right subtree has one internal node (3). The recursive calls will return these counts.
- Finally, the function will return 1, indicating the root node itself is an internal node.
- Therefore, the total count of internal nodes in this tree is 1 (root) + 2 (left subtree) + 1 (right subtree) = 4.
Hence, the correct answer is option 'B', which states that the function counts internal nodes.
What does the following function do for a given binary tree?int fun(st...
As for leaf node the root.left and root.right would be
null , only for internal nodes,we add the no of nodes in left and right.
therefore counts no of internal nodes
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).