Valid Binay Tree


#1

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

a. (12(4567)) b.(1((234)56)7) c. (1(234)(567)) d. (1(23NULL)(45))


#2

C is correct.

  •          1
    
  •      2        5
    
  •    3   4    6    7
    

Try to draw the others too.


#3

@Anmol_Binani

Can you please tell me how you construct the tree ?


#4

Sure @prateek111
Look at the representation given: ( X Y Z )
It is said here that X is the node, Y is the left subtree and Z is the left subtree.
It is also said the Y & Z can either be nested or NULL.

so, let us see option C: ( 1 ( 2 3 4 ) ( 5 6 7 ) )
now consider:
1 --> X,
( 2 3 4 ) --> Y,
( 5 6 7 ) --> Z.

We get:

  •                   ( 1 )
    
  •         ( 2 3 4 )        ( 5 6 7 )
    

Now we can clearly see that ( 2 3 4 ) & ( 5 6 7) are clearly in the form of ___( X Y Z )___.
So we will again expand them too, as:

  •      2                    
    
  •   3     4  
    

and

  •      5
    
  •   6     7
    

Hence the complete answer will be as mentioned:

  •                         1
    
  •                    2          5
    
  •                 3     4    6     7
    

I hope you got it.
Do try the rest and you will find the difference.


#5

@Anmol_Binani
Can you please check my tree for other options, and correct me if it is wrong…

(b) (1((234)56)7)

                            (1)

                   (2)                (7)

         (3)             (4) 

 (5)                             (6)

d. (1(23NULL)(45))

                             (1)
                     
                    (2)               (4)

             (3)                 (5)

a. (12(4567))

                       (1)

               (2)             (4567)

#6

@prateek111 you can’t construct the binary tree with all the other options other than c.

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 D :
(4567) doesn’t follow the rule (XYZ).

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.

So according to the representation we will only be able to draw binary tree for option c.

Now look at the figures you have constructed. Since you were able to draw binary tree for options a & d they also seem to be a valid binary tree because in your figure, both these trees follow the Rule of at most 2 childern.

I hope you understood how to solve this question.