GATE Overflow | Data Structures | Test 1 | Question: 25

Question

Consider the following nested representation of Binary Trees.

$(ABC)$ indicates $B$ and $C$ are left and right subtrees of node $A$ respectively. Note that $B$ and $C$ may be NULL or further nested.

Which of the following representation is not a valid Binary tree?    
 

• A. (1 2 3)  
• B. (1 (2 3 4) (5 6 7))         
• C. (1 (1 (1 1 1) (1 1 1)) (1 1 1))     
• D. (1 (2 3) 4)

Answer 1

in option d we have (2 3).. we do not know which is the middle element and binary tree is not defined for such case in the question.

all other options do not have any such case..

Comments

as in question it is specified that from ABC, only B or C can be null. Now, in (2,3) 2 is root and 3 can be eithe right child or left child of 2 and other child is null. here nowhere mention that tree must have 2 children, so this also a valid binary tree. may be other issue in D option, but not atleast what you have explained

Answer 2

Option D should also be correct as (2 3) means root = 2 , left child= 3 , right child = null so writing (2 3 null) is same as writing (2 3)