SDE - Intern

You are provided with a Binary Tree and one of its leaf nodes. You have to invert this binary tree. Inversion must be done by following all the below guidelines:

• The given leaf node becomes the root after the inversion.

• For a node (say, ‘x’) 
    ○ If there exists the left child that is not yet taken then this child must become the right child of ‘x’.
    ○ If the left child is already taken then the right child is still on the right side of ‘x’.

• The parent of ‘x’ must be the left child of ‘x’.

For Example:

Consider the above binary tree (image- before inversion), if the given leaf node is ‘1’ then the binary tree after inversion becomes exactly the same as given in the image representing after inversion.

Note:

The given binary tree will only have distinct values of nodes.

For a given Singly Linked List of integers, you are required to reverse alternate nodes and append them to the end of the list.

For Example:

The given linked list is 1->2->3->4 then after reversing the alternate nodes we will have 1->3->4->2. 

Assuming 0 based indexing, odd indexed nodes are the alternate nodes that is, in the given linked list the node with value 2 and the node with value 4 are the alternate nodes. 

List without alternate nodes:  1->3 
List with alternate nodes:  2->4 
Reversing the list with alternate nodes: 4->2

After appending the reversed alternate nodes at the end, the updated list will be 1->3->4->2.