- Theory
- Questions
- Given a binary tree, populate an array to represent its level-by-level traversal. You should populate the values of all nodes of each level from left to right in separate sub-arrays.
- Given a binary tree, populate an array to represent its level-by-level traversal in reverse order, i.e., the lowest level comes first. You should populate the values of all nodes in each level from left to right in separate sub-arrays.
- Given a binary tree, populate an array to represent its zigzag level order traversal. You should populate the values of all nodes of the first level from left to right, then right to left for the next level and keep alternating in the same manner for the following levels.
- Given a binary tree, populate an array to represent the averages of all of its levels.
- Find the minimum depth of a binary tree. The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.
- Given a binary tree and a node, find the level order successor of the given node in the tree. The level order successor is the node that appears right after the given node in the level order traversal.
- Given a binary tree, connect each node with its level order successor. The last node of each level should point to a null node.
- Given a binary tree, connect each node with its level order successor. The last node of each level should point to the first node of the next level.
- Given a binary tree, return an array containing nodes in its right view. The right view of a binary tree is the set of nodes visible when the tree is seen from the right side.

We keep count of the number of nodes in the level and run a loop for that number to get only the nodes of that level from the queue.

**Implementation: LevelOrderTraversal**

To keep track of the level, we count how many elements we are putting in the queue, per level and then use that cnt to poll elements to print as well.

`O(n)`

`O(n)`

for the queue.

**Implementation: ReverseLevelOrderTraversal**

Exactly the same as before, except we add the results to the head of a LinkedList.

`O(n)`

`O(n)`

for the queue.

**Implementation: ZigZagTraversal**

The order of printing is:

- left-to-right
- right-to-left
- left-to-right
- .... and so on

Same as the others. For the reverse direction, we use a LinkedList and append to the head.

`O(n)`

`O(n)`

**Implementation: LevelAverages**

Same as before, instead of add the node values to the list, we sum and average it with the `levelCnt`

.

`O(n)`

`O(n)`

**Implementation: MinDepth**

Same as before. To calculate the minDepth, we compare the depth of every leaf node if its the node with the min depth.

`O(n)`

`O(n)`

**Implementation: LevelOrderSuccessor**

Since it just wants the level order successor, we need to iterate in level order till we find the key, and return the next element.

`O(n)`

`O(n)`

**Implementation: ConnectLevelOrderSiblings**

As we traverse through each node in a level, we need to connect it to the next node in the level. The end node connects to null.

`O(n)`

`O(n)`

**Implementation: ConnectAllLevelOrderSiblings**

Same as above, except here we dont need to keep track of the levels.

`O(n)`

`O(n)`

**Implementation: RightView**

This is the last element in the level. So we can go level-by-level and capture the last element.

`O(n)`

`O(n)`