Solution


Approach #1 Using Depth First Search [Accepted]

Algorithm

One of the methods to solve the given problem is to make use of Depth First Search. In DFS, we try to exhaust each branch of the given tree during the tree traversal before moving onto the next branch.

To make use of DFS to solve the given problem, we make use of two lists and . Here, refers to the total number of nodes found at the level(counting from root at level 0) till now, and refers to the sum of the nodes at the level encountered till now during the Depth First Search.

We make use of a function average(t, i, res, count), which is used to fill the and array if we start the DFS from the node at the level in the given tree. We start by making the function call average(root, 0, res, count). After this, we do the following at every step:

  1. Add the value of the current node to the (or ) at the index corresponding to the current level. Also, increment the at the index corresponding to the current level.

  2. Call the same function, average, with the left and the right child of the current node. Also, update the current level used in making the function call.

  3. Repeat the above steps till all the nodes in the given tree have been considered once.

  4. Populate the averages in the resultant array to be returned.

The following animation illustrates the process.

!?!../Documents/637_Avg_of_Levels_DFS.json:1000,563!?!

Complexity Analysis

  • Time complexity : . The whole tree is traversed once only. Here, refers to the total number of nodes in the given binary tree.

  • Space complexity : . and array of size are used. Here, refers to the height(maximum number of levels) of the given binary tree. Further, the depth of the recursive tree could go upto only.


Approach #2 Breadth First Search [Accepted]

Algorithm

Another method to solve the given problem is to make use of a Breadth First Search. In BFS, we start by pushing the root node into a . Then, we remove an element(node) from the front of the . For every node removed from the , we add all its children to the back of the same . We keep on continuing this process till the becomes empty. In this way, we can traverse the given tree on a level-by-level basis.

But, in the current implementation, we need to do a slight modification, since we need to separate the nodes on one level from that of the other.

The steps to be performed are listed below:

  1. Put the root node into the .

  2. Initialize and as 0 and as an empty queue.

  3. Pop a node from the front of the . Add this node's value to the corresponding to the current level. Also, update the corresponding to the current level.

  4. Put the children nodes of the node last popped into the a queue(instead of ).

  5. Continue steps 3 and 4 till becomes empty. (An empty indicates that one level of the tree has been considered).

  6. Reinitialize with its value as .

  7. Populate the array with the average corresponding to the current level.

  8. Repeat steps 2 to 7 till the and become empty.

At the end, is the required result.

The following animation illustrates the process.

!?!../Documents/637_Average_Of_Levels.json:1000,563!?!

Complexity Analysis

  • Time complexity : . The whole tree is traversed atmost once. Here, refers to the number of nodes in the given binary tree.

  • Space complexity : . The size of or can grow upto atmost the maximum number of nodes at any level in the given binary tree. Here, refers to the maximum mumber of nodes at any level in the input tree.


Analysis written by: @vinod23