Test: Trees- 2 - Computer Science Engineering (CSE) MCQ

Let there be n(h) nodes at height h.
In a perfect tree where every node has exactly two children, except leaves, following recurrence holds.
n(h) = 2*n(h-1) + 1
In given case, the numbers of nodes are two less, therefore
n(h) = 2*n(h-1) + 1 - 2
= 2*n(h-1) - 1 Now if try all options, only option (b) satisfies above recurrence.
Let us see option (B) n(h) = 2^{h - 1} + 1
So if we substitute n(h-1) = 2^h-2 + 1, we should get n(h) = 2^h-1 + 1
n(h) = 2*n(h-1) - 1
= 2*(2^h-2 + 1) -1
= 2^h-1 + 1.

It would be node number 31 for given distance 4. For example if we consider at distance 2, below highlighted node G can be the farthest node at position 7.

In a binary tree, the number of leaf nodes is always 1 more than number of internal nodes with 2 children, refer
So, Number of Leaf Nodes = Number of Internal nodes with 2 children + 1 Number of Leaf Nodes = 10 + 1 Number of Leaf Nodes = 11

The approach to solve this question is to first find 2 sequences whose first and last element is same. The reason being first element in the Pre-order of any binary tree is the root and last element in the Post-order of any binary tree is the root. Looking at the sequences given,
Pre-order = KAMCBYPFH Post-order = MBCAFHPYK Left-over sequence MABCKYFPH will be in order. Since we have all the traversals identified, let's try to draw the binary tree if possible.

I. Post order
II. Pre order
III. Inorder

If a tree is not empty, height of tree is MAX(Height of Left Subtree, Height of Right Subtree) + 1 See program to Find the Maximum Depth or Height of a Tree for more details.

The order of inorder traversal is LEFT ROOT RIGHT The order of preorder traversal is ROOT LEFT RIGHT The order of postorder traversal is LEFT RIGHT ROOT In all three traversals, LEFT is traversed before RIGHT

Below is the given tree.

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.

Let us consider the given expression ([Tex]7 downarrow 3 uparrow 4 uparrow 3 downarrow 2[/Tex]). Since the precedence of [Tex]uparrow[/Tex] is higher, the sub-expression ([Tex]3 uparrow 4 uparrow 3[/Tex]) will be evaluated first. In this sub-expression, [Tex]4 uparrow 3[/Tex] would be evaluated first because [Tex]uparrow[/Tex] is right to left associative. So the expression is evaluated as [Tex]((7 downarrow (3 uparrow (4 uparrow 3))) downarrow 2)[/Tex]. Also, note that among the two [Tex]downarrow [/Tex] operators, first one is evaluated before the second one because the associativity of [Tex]downarrow[/Tex] is left to right.

Breadth first search visits all the neighbors first and then deepens into each neighbor one by one. The level order traversal of the tree also visits nodes on the current level and then goes to the next level.

Level order traversal uses a queue data structure to visit the nodes level by level.

To generate a binary tree, two traversals are necessary and one of them must be inorder. But, a full binary tree can be generated from preorder and postorder traversals. Read the algorithm here. Read Can tree be constructed from given traversals?

Explanation: DoSomething() returns max(height of left child + 1, height of left child + 1). So given that pointer to root of tree is passed to DoSomething(), it will return height of the tree. Note that this implementation follows the convention where height of a single node is 0

The correct option is D LASTIN = LASTPRE
Because of complete binary tree option (D) is always correct

 Explanation: The level order traversal of a binary tree prints the data in the same order as it is stored in the array representation of a complete binary tree.

Algorithm Inorder(tree) - Use of Recursion Steps:
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Understanding this algorithm requires the basic understanding of Recursion
Therefore, We begin in the above tree with root as the starting point, which is P.
# Step 1( for node P) :
Traverse the left subtree of node or root P.
So we have node Q on left of P.
-> Step 1( for node Q)
Traverse the left subtree of node Q.
So we have node S on left of Q.
* Step 1 (for node S)
Now again traverse the left subtree of node S which is NULL here.
* Step 2(for node S)
Visit the node S, i.e print node S as the 1st element of inorder traversal.
* Step 3(for node S) Traverse the right subtree of node S.
Which is NULL here.

Now move up in the tree to Q which is parent of S.( Recursion, function of Q called for function of S).
Hence we go back to Q.
-> Step 2( for node Q):
Visit the node Q, i.e print node Q as the 2nd element of inorder traversal.
-> Step 3 (for node Q) Traverse the right subtree of node Q.
Which is NULL here.
Now move up in the tree to P which is parent of Q.( Recursion, function of P called for function of Q).
Hence we go back to P.
# Step 2(for node P)
Visit the node P, i.e print node S as the 3rd element of inorder traversal.

# Step 3 (for node P) Traverse the right subtree of node P.
Node R is at the right of P.

Till now we have printed SQP as the inorder of the tree. Similarly other elements can be obtained by traversing the right subtree of P.

The final correct order of Inorder traversal would be SQPTRWUV.

The function counts leaf nodes for a tree represented using leftMostChild-rightSibling representation. Below is function with comments added to demonstrate how function works. [sourcecode language="C"] int DoSomething (treeptr tree) { // If tree is empty, 0 is returned int value = 0; // IF tree is not empty if (tree != NULL) { // IF this is a leaf node, then values is initialized as 1 if (tree->leftMostChild == NULL) value = 1; // Else value is initialized as the value returned by leftmost // child which in turn calls for the other children of this node // Using last call "value = value + DoSomething(tree->rightSibling);" else value = DoSomething(tree->leftMostChild); // Add value returned by right sibling value = value + DoSomething(tree->rightSibling); } return(value); }[/sourcecode]

Here, we consider each and every option to check whether it is true or false. 1) Preorder and postorder

For the above trees, Preorder is AB Postorder is BA It shows that preorder and postorder can’t identify a tree uniquely. 2) Inorder and postorder define a tree uniquely 3) Preorder and Inorder also define a tree uniquely 4) Levelorder and postorder can’t define a tree uniquely. For the above example, Level order is AB Postorder is BA See 

The correct option is D LASTIN = LASTPRE
Because of complete binary tree option (D) is always correct

Inorder Traversal: Left -Root -Right PreOrder Traversal: Root-Left-Right

InOrder PreOrder
 

A.   BADC   ABCD
B.   BCAD   ACBD
C.   ACBD   ABCD
D.    BCAD  ABCD

Therefore, D is Correct

Binary Search Tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree. There must be no duplicate nodes.

So let us say n=10, p=4. According to BST property the root must be 10-4=6 (considering all unique elements in BST)

And according to BST insertion, root is the first element to be inserted in a BST.

Therefore, the answer is (n-p).

As here we want subset of edges that connects all the vertices and has minimum total weight i.e. Minimum Spanning Tree Option A - includes cycle, so may or may not connect all edges. Option B - has no relevance to this question. Option C - includes cycle, so may or may not connect all edges. Related

There are two set of values, smaller than 60 and greater than 60. Smaller values 10, 20, 40 and 50 are visited, means they are visited in order. Similarly, 90, 80 and 70 are visited in order. 
= 7!/(4!3!)
= 35

a full binary tree is a binary tree in which all nodes except leaves have two children.

In a Full Binary, number of leaf nodes is number of internal nodes plus 1

L = I + 1

Where L = Number of leaf nodes, I = Number of internal nodes

1: abef->c or g should be covered
4: adbc->e or f should be covered 
2: abefcgd correct
3: adgebcf correct