SDE

Approach 1 (Using Level Order Traversal) : 

Steps : 
1) Initialize an array ‘spiral’ to store the result.
2) Initialize a variable ‘direction’ to keep track of traversing direction with 1(denoting left to right)
3) Find the height of the given tree and store it in a variable ‘height’.
4) Run a loop - level : 1 to height, to traverse through every level.
4.1) Find level order traversal in the current direction.and store in ‘spiral’
4.2) Toggle the direction.
5) Return ‘spiral’

TC : O(N^2), where ‘N’ is the number of nodes in the binary tree.
SC : O(h), where 'h' is the height of the binary tree.

Approach 2 (Using Stack) :

Steps : 
1) We will maintain two stacks, one for each direction i.e. leftToRight and rightToleft.
2) We will do a level order traversal of the given binary tree and push nodes of each level onto one of the 
stack according to the current direction of traversal.
3) After we’ve pushed all nodes of a level onto one stack, we’ll start popping those nodes. 
4) While popping the nodes we will push their children (if any) onto our other direction stack, so that the 
next level be traversed in reverse order.

TC : O(N), where ‘N’ is the number of nodes in the binary tree.
SC : O(N)

Answer : 

Structure : Structure is a user-defined data type in C programming language that combines logically related data items of different data types together.
All the structure elements are stored at contiguous memory locations. Structure type variable can store more than one data item of varying data types under one name.

Union : Union is a user-defined data type, just like a structure. Union combines objects of different types and sizes together. The union variable allocates the memory space equal to the space to hold the largest variable of union. It allows varying types of objects to share the same location.

Key differences b/w Structure and Union : 

1) Every member within structure is assigned a unique memory location while in union a memory location is shared by all the data members.

2) Changing the value of one data member will not affect other data members in structure whereas changing the value of one data member will change the value of other data members in union.

3) Structure is mainly used for storing various data types while union is mainly used for storing one of the many data types.

4) In structure, you can retrieve any member at a time on the other hand in union, you can access one member at a time.

5) Structure supports flexible array while union does not support a flexible array.



Advantages and Disadvantages of using Structure : 

Advantages : 
1) Structures gather more than one piece of data about the same subject together in the same place.
2) It is helpful when you want to gather the data of similar data types and parameters like first name, last 
name, etc.
3) It is very easy to maintain as we can represent the whole record by using a single name.

Disadvantages :
1 )If the complexity of IT project goes beyond the limit, it becomes hard to manage.
2) Change of one data structure in a code necessitates changes at many other places. Therefore, the 
changes become hard to track.
3) Structure is slower because it requires storage space for all the data.

You are given a Binary Tree. You are supposed to return the length of the diameter of the tree.

Approach : I solved this problem using BFS.

Breadth-First-Search considers all the paths starting from the source and moves ahead one unit in all those paths at the same time. This makes sure that the first time when the destination is visited, it is the path with the shortest length.

Steps : 

1) Create an empty queue and enqueue source cell and mark it as visited
2) Declare a ‘STEPS’ variable, to keep track of the length of the path so far
3) Loop in level order till the queue is not empty
3.1) Fetch the front cell from the queue
3.2) If the fetched cell is the destination cell, return ‘STEPS’
3.3) Else for each of the 4 adjacent cells of the current cell, we enqueue each valid cell into the queue 
and mark them visited.
3.4) Increment ‘STEPS’ by 1 when all the cells in the current level are processed.
4) If all nodes in the queue are processed and the destination cell is not reached, we return -1.

TC : O(N*M), where ‘N’ and ‘M’ are the number of rows and columns in the Binary Matrix respectively.
SC : O(N*M)