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). 2¹⁰-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 2^h-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). Ω(n²)

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). 2^k-1
(B). 2^k-1
(C). 2^k
(D). 2^k+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 log₂n
(B). About 2log₂n
(C). About nlog₂n
(D). About 2n

Ans:-A

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

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) 2⁰+2¹+......+2^h
(B) 2⁰+2¹+......+2^h-1
(C) 2⁰+2¹+......+2^h+1
(D) 2¹+......+2^h+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+....2^h-1+2^h

JUNE 2012 PAPER III Q.No 36

Already discussed in JUNE 2012 PAPER III solution...

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.