GATE CSE 2000 | Question: 1.14

Question

Consider the following nested representation of binary trees: $(X \ Y \ Z)$ indicates $Y$ and $Z$ are the left and right subtrees, respectively, of node $X$. Note that $Y$ and $Z$ may be $NULL$, or further nested. Which of the following represents a valid binary tree?

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

Comments

If we modify B like this (1 ( ( 234 ) 5 6 ) 7 ) then also It will be invalid.

---

An easy technique for this is to substitute 3-number pairs in a bracket with a variable.

So, A becomes (1 2 (a 7)). Now we can't have (a 7), so error
On the other hand, C becomes (1 (2 3 4) (5 6 7)) => (1 a b) => c. So, a valid binary tree
We can similarly do it for options B and D

---

option D is not left filled in right subtree

Answer 1

• A. $\rightarrow  (4 \ 5 \ 6 \ 7)$ this part of answer is not correct. We have $(X \ Y \ Z)$ not $ (W \ X \ Y \ Z)$. So, this is wrong
• B. $\rightarrow 3$ closing paranthesis, $2$ opening paranthesis. This is wrong. 
• C. $\text{CORRECT}$ 
• D. $\rightarrow$ Here in $(1 \ (2 \ 3 \ NULL) \ (4 \ 5)) , (4 \ 5)$ this is not allowed. So this is wrong. (It should be $(4,5,NULL)$)

Comments

In B) actually tree is not (XYZ) format.
Only parenthesis can be the correct reason?@Arjun Sir

---

nice akash sir,sir i think for option B) srestha mam's reason true

---

I have an doubt, in question they mention it was a binary tree,

When we construct the tree 234, 2 has left child 3, which is not valid,

in binary tree leftchild <= root && right child >= root.

In this case it was failing the basic condtion of binary tree.

Suppose if we construct tree 234 as  2(root)-> 3(RST) -> 4(RST), then it fails to be complete binary tree, but in qustn it was mentioned that it was complete tree.

 

Correct me if i am wrong and adds value if solution is provided.

Thanks in advance.

---

@katari

What your definition says is the definition of Binary Search Tree and not of binary tree.

There is a difference between Binary tree and Binary search tree. Binary tree says every node has atmost 2 children thats it.

 

https://stackoverflow.com/questions/6380231/difference-between-binary-tree-and-binary-search-tree

 

Answer 2

Option C is Ans  as it generates a valid binary tree as shown below fig.

No other option is eligible for given constraints of question.

               

Comments

(X Y Z) indicates Y and Z are the left and right subtrees, respectively, of node X .... Its basically preorder sequence ...

---

What will be the case for Option D
Rajesh Pradhan plz explain ??

Answer 3

To solve this question we have to look at two things: 1) In a binary tree, a node may have at most 2 children. 2) To construct binary tree from the given sequences above, innermost parenthesis should be worked first.

In Option A : ( 4 5 6 7 ) is there, which says that node 4 has got three children, which is wrong for a binary tree, and also in the question, only ( X Y Z ) is defined, i.e. a node X can have at most 2 children, which will be the roots of subtrees Y and Z.

In Option B : after working on innermost (2 3 4), where 2 is a node of the binary tree, 3 is left subtree of node 2 and 4 is right subtree of node 2. From this we get (1 2 5 6). Here 2 has come from the root of subtree ( 2 3 4 ). Now again we don't have any definition for ( 1 2 5 6). Hence invalid.

In Option C: after working on ( 2 3 4) and ( 5 6 7 ) we get ( 1 2 5 ) where 2 has come from the root of subtree ( 2 3 4 ) and 5 has come from the root of subtree ( 5 6 7 ). Now, in ( 1 2 5 ) node 1 is the root of the binary tree, and subtree with root 2 is the left subtree and subtree with root 5 is the right subtree at root node 1. Hence it is giving valid binary tree.

In Option D: It is given as ( 2 3 NULL), here N,U,L and L are given as different elements, which is again wrong as according to ( X Y Z) definition, a node can have at most 2 children.

Source :geeksforgeeks

Answer 4

So answer is C

Caption

 

Answer 5

ans c)

Comments

How did u solve that ?

Answer 6

We can only construct from C option so c is answer