Theory

Keeping level count

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.

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.

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.

Time complexity

O(n)

Space complexity

O(n) for the queue.

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.

Implementation: ReverseLevelOrderTraversal

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

Time complexity

O(n)

Space complexity

O(n) for the queue.

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.

Implementation: ZigZagTraversal

The order of printing is:

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

Time complexity

O(n)

Space complexity

O(n)

Given a binary tree, populate an array to represent the averages of all of its levels.

Implementation: LevelAverages

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

Time complexity

O(n)

Space complexity

O(n)

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.

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.

Time complexity

O(n)

Space complexity

O(n)

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.

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.

Time complexity

O(n)

Space complexity

O(n)

Given a binary tree, connect each node with its level order successor. The last node of each level should point to a null node.

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.

Time complexity

O(n)

Space complexity

O(n)

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.

Implementation: ConnectAllLevelOrderSiblings

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

Time complexity

O(n)

Space complexity

O(n)

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.

Implementation: RightView

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

Time complexity

O(n)

Space complexity

O(n)

Return to Index