3.8k views

Which of the following statements is false?

1.  A tree with a $n$ nodes has $(n – 1)$ edges
2.  A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.
3.  A complete binary tree with $n$ internal nodes has $(n + 1)$ leaves.
4.  The maximum number of nodes in a binary tree of height h is $2^{h+1} - 1$
in DS
edited | 3.8k views
+2

1. Strict binary tree :

$\rightarrow$ Every node of tree must have either 0 or 2 child

2. Complete binary tree :

$\rightarrow$ CBT of $l$ levels must have $l-1$ levels fully occupied

$\rightarrow l^{th}$ level nodes can be added left to right

$\rightarrow$ CBT of height h has $2^h$ to $2^{h+1}-1$ nodes

3. Full binary tree :

$\rightarrow$ Every node must have 0 or 2 child and all the leaf nodes must be at the same level.

$\rightarrow$ CBT of height h has $2^{h+1}-1$ nodes

$*$ Every FBT is CBT

$In\ question\ sometimes:$

$CBT\rightarrow ACBT$

$FBT\rightarrow CBT$

• Tree with $n$ nodes must have $n-1$ edges.
• A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results. (inorder must be needed with either preorder or postorder for that)
• A complete binary tree with $n$ nodes can have $n$ leaves also
• Example:

Since: A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. So false

•  The maximum number of nodes in a binary tree of height $h$ is

$1+2+4+.....+2^h=2^{h+1}-1$ So true

Answer is b and c both.

Since, $2$ answers are there I would choose b, because in some places by "complete" binary tree they mean "full binary tree" which has all the levels completely filled.

by Boss
edited
+2
Splendid !!!
+11
This is "almost complete"   so only B should be the answer.
No worries, in gate definitely they will mention the definition of "complete" every time.
+1
By complete binary tree they mean every node can have either two children or none, it cannot have one child.
0
if you analyze other gate questions then complete binary tree should have either 2 or zero child so if they are not defining it , we should assume this definition  only, i think.

so only option b is false
0
B and C both are false.

Only BST can be constructed with either pre-order or post-order.

C is false because, take an example with n = 2. It's a complete binary tree but has 1 internal and 1 leaf node, which contradicts the statement.
0
but here what you define it is almost complete binary tree..
+2

A complete binary tree with n internal nodes has n+1 leaves.

This statement is not false.

Because it clearly mentions 'complete binary tree'  not Nearly complete binary tree.

Cormen differentiates it well.

So, only B is false and answer too.

+1
A complete binary tree with n nodes can have n leaves also .

Can anyone give some example for this kind of tree .
+1
Draw tree with $2$ and $1$ nodes.
A) True

B) From a given inorder and preorder/postorder a binary tree can be constructed. By preorder or post oredr binary tree not possible to construct. Hence False.

C) A complete binary tree of height h( say)

Total internal nodes 1+2+4+8+....+ 2^h-1=2^h-1=n

=>2^h=n+1

2^h is nothing but total number of leaves in tree hence  C is true

D) 1+2+4+.....+2^h=2^h+1-1    ( True )
by Active
0
For c) ...why root is considered as internal root?
+2
@srestha c should be false .. since it is not full binary tree..so there is not such condition that each node having 0 or 2 children..
0
@srestha it should be both b and c , right ?
c should be false
0
Then multiple choice ans was possible
0
@srestha actually not for this. That was for GATE 1999 only.
0
yes then B) should be answer.

Because only BST we can construct the tree from only postorder or preorder traversal.

For binary tree it is not possible
+2
yes, b is the one you should pick for exam. C could be true based on definition. Also we do not know the exact question which was asked as that is not stored anywhere now.
option (b) and (c) are false ,

for option (c) since last level of complete tree need not be full.

counter example (1) make complete tree of 2 node ,

counter example (2) make complete tree of 4 node
by Active
reshown by

both b and c are false

For c - no of internal nodes  = 6 and no of leaves = 6

by Junior
0
Here by complete binary tree, they mean all the levels must be completely filled, so C is true
ans b)
by Active
–1 vote

Option C will be true in case of strictly binary tree in which each non leaf node has non empty left and right child.

by Loyal