Showing posts with label Data Structures. Show all posts
Showing posts with label Data Structures. Show all posts

Friday, 19 June 2015

DECEMBER 2010 - QUESTION NO 25

This particular question is not clear for few readers. So, I am taking it up once again.

25. Which of the following can be the sequence of nodes examined in binary search tree while searching for key 88 ?

(A) 90, 40, 65, 50, 88
(B) 90, 110, 80, 85, 88
(C) 190, 60, 90, 85, 88
(D) 65, 140, 80, 70, 88

Ans:- B

Explanation:-
I am taking the liberty of retaining an explanation given for a similar question from yahoo answers.

Best Answer: For a binary search tree, the entire tree is sorted such that for any node, every node to the left is less than the current node value and every node to the right is more than the current node value.

When walking a BST tree, you "zero in" on the value by following the correct nodes down the tree. Ideally you work closer and closer to your answer, kind of like the "guess the number" game where you give "nope, more!" and "nope, less!" hints.

a) 2, 399, 387, 219, 266, 382, 381, 278, 363
This sequence is possible.

b) 935, 278, 347, 621, 299, 392, 358, 363
This sequence is not possible. Since 621 is to the right of 347, every other node under 621 must ALSO be to the right of 347. 299 is not -- so this is an impossible walk. Basically, once you pass 347, 299 is swinging too far in the opposite direction.

c) 924, 220, 911, 244, 898, 258, 362, 363
This sequence is possible.

d) 925, 202, 911, 240, 912, 245, 363
Not possible -- 240 is to the left of 911, so every other node must also be less than 911 (but still may be to the right of 240). 912 is not to the left of 911.

e) 2, 252, 401, 398, 330, 344, 397, 363 This sequence is possible. Just barely though -- 397 is to the left of 398 but just barely!

I am taking the example b which explains why a particular sequence is not possible. Since 621 is to the right of 347, every other node under 621 must ALSO be to the right of 347.

Let us apply the same rule to all the sequences given above for us in the question.
The first sequence is 90,40,65,50,88. Do not consider any particular element as the root. But start analysing the numbers from first. 90 is the first number. 40 is the second one. So, 40 will be to the left of 90, since it is less than 90. Since 40 is to the left of 90, all numbers following 40 also should be to the left of 90, which is true in this sequence. 65,50, and 88 will be to the left of 90. So this sequence is possible.

Let us consider the second sequence which is 90,110,80,85,88. Again 90 is the first number. 110 will be to its right since it is greater than 90. So all the numbers following 110 also should be to the right of 90,but 80,85 and 88 fall to its left. So, this sequence is not possible.

Let us consider the third sequence which is 190,60,90,85,88. So, 190 is the first number. 60 is to its left. So all the other numbers following 60 should be to the left of 190, which is holding good here. 90,85 and 88 will be to the left of 190. So, this sequence is possible.

Let us consider the fourth sequence which is 65,140,80,70,88. 65 is the first number. 140 will be to its right. All the numbers following 140 should be to the right of 65 which is true. 80,70 and 88 will be to the right of 65 as well.

So, the correct answer is option B and not C.
Thank you all, for bringing this question for discussion as we have zeroed in on the right answer.

Monday, 23 March 2015

PROPERTIES OF BINARY TREES

PROPERTIES OF BINARY TREES

There are some basic properties of binary trees. It is better to know all of them and how to apply.For easier understanding I am giving it in a tabular form.

1. Maximum number of nodes on any level i is 2i
2. Maximum number of nodes possible in a binary tree of height h is 2h-1
3. Minimum number of nodes possible in a binary tree of height h is equal to h
4. If a binary tree contains n nodes, then its maximum height possible is n
5. If a binary tree contains n nodes, then its minimum height possible is log2(n+1)
6. In a non empty binary tree, if n is the total number of nodes and e is the total number of edges, then e=n-1
7. In a full binary tree of height k, there are 2k-1 internal nodes
8. A strictly binary tree with n leaf nodes always has 2n - 1 nodes

JUNE 2007 - PAPER II Q.No 3


The maximum number of nodes in a binary tree of depth 10 is :
(A). 1024
(B). 210-1
(C). 1000
(D). None of the above

Ans:- B

Explanation:-
According to property 2, the maximum number of nodes in a binary tree of height or depth h is 2h-1

DECEMBER 2007 - PAPER II Q.No 23


The height of a binary tree with 'n' nodes in the worst case is

(A). 0(log n)
(B). O(n)
(C). Ω(n log n)
(D). Ω(n2)

Ans:- B

Explanation:-
Big omega notation is used for representing the best case. Big oh notation is used for representing the worst case. It is a measure of the longest amount of time it could possibly take for any algorithm to complete. Since we are representing the height of a binary tree, it would be the maximum height possible in a tree with 'n' nodes and it is O(n). So, the correct answer is B.

JUNE 2009 - PAPER II Q.No. 27


In a full binary tree of height k, there are ____________internal nodes.

(A). 2k-1
(B). 2k-1
(C). 2k
(D). 2k+1

Ans:-A

Explanation:-
Refer to the following diagram to understand the explanation. A full binary tree is one which has all the levels have maximum number of nodes in a tree.

DECEMBER 2009 - PAPER II Q.No 21

If the number of leaves in a strictly binary tree is an odd number, then what can you say with full conviction about total number of nodes in the tree?.
(A). It is an odd number.
(B). It is an even number.
(C). It cannot be equal to the number of leaves
(D). It is always greater than twice the number of leaves

Ans:-A

Explanation:-
A binary tree is a strictly binary tree if each node in the tree is either a leaf node or has exactly two children. There is no node with one child. According to its property, a strictly binary tree with n leaf nodes always has 2n-1 nodes. Let us consider n to be an odd number and give it a value of 3. So, the number of nodes in the tree would be 2n - 1 which is 2 X 3 -1 = 5. So that is also an odd number. So, the answer is A.

JUNE 2010 - PAPER II Q.No 23

In a complete binary tree of n nodes, how far are the two most distant nodes?.Assume each edge in the path count as 1.
(A). About log2n
(B). About 2log2n
(C). About nlog2n
(D). About 2n

Ans:-A

Explanation:-
The height h of a complete binary tree with n nodes is at the most O(log2n).

DECEMBER 2011 - PAPER II Q.No. 50

The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to

(A) 20+21+......+2h
(B) 20+21+......+2h-1
(C) 20+21+......+2h+1
(D) 21+......+2h+1

Ans:-A

Explanation:-
Count the number of nodes in each level, starting with the root, assuming that each level has the maximum number of nodes.
n=1+2+4+....2h-1+2h

JUNE 2012 PAPER III Q.No 36

Already discussed in JUNE 2012 PAPER III solution...

Wednesday, 11 March 2015

CONVERSION OF INFIX EXPRESSION TO POSTFIX EXPRESSION

The conventional method of representing an arithmetic expression is known as infix because the operand is placed in between the operands. If the operator is placed before the operands then this notation is called prefix or Polish notation. If the operator is placed after the operand then this notation is called postfix or reverse polish notation. So now we have three ways to represent an arithmetic expression.

Infix:   A+B

Prefix:   +AB

Postfix:   AB+

Now, let us see how to convert an infix expression to postfix expression. The rules of parenthesis and precedence would be followed in the following way. If there are parenthesis in the expression, then the portion inside the parenthesis will be converted first. After this the operations are converted according to their precedence. (* and / first, followed by + and -). If there are operators of equal precedence then the operator which is on the left is converted first. In order to understand this with an example, let us solve an example from June 2014, Paper III, Question No. 41.

JUNE 2014 - PAPER III - Q.No 41

41. The reverse polish notation equivalent to the infix expression

((A + B) * C + D) / (E + F + G)

(A) A B + C * D + E F + G + /

(B) A B + C D * + E F + G + /

(C) A B + C * D + E F G + +/

(D) A B + C * D + E + F G + /

Ans:-A

Explanation:-

First, always the expression given within parenthesis is converted first. Since there are 2 expressions with the parenthesis, I am going with the expression (E + F + G) first, although the order does not matter.

In the expression (E + F + G), there are 3 operands E,F and G and two operators, both being +. Since both the operators are the same, the expression is going to be evaluated from left to right. So E + F is considered first and converted into postfix form which is EF+. So, the expression becomes,

( ( A + B ) * C + D) / ([E F +] + G)

Any expression converted into postfix form is going to be written in square brackets.

( ( A + B ) * C + D) / [ E F + G + ]
. Here EF+ is one operand, G is another operand and + is the operator.

The next expression to be converted into postfix is ( A + B).

( [ A B + ] * C + D) / [ E F + G + ]

Now, the expression which is enclosed in parenthesis is evaluated and so, we get

( [ [ A B + ] C * ] + D) / [ E F + G + ]

[ A B + C * D + ] / [ E F + G + ]

[ A B + C * D + ] [ E F + G + ] /

So, the final postfix expression is A B + C * D + E F + G + /. This answer is available in option A. So option A is the correct answer.