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...