Binary Tree Average Per Level - Alternative Solution (from https://www.facebookrecruiting.com)
This is an alternative implementation for the Binary Tree Average Per Level problem available at Meta Preparation Hub Site.
The problem is really simple, given a binary tree, find all the averages of its nodes per level.
In the test case example, we have the following binary tree, and we have to find its corresponding levels for each one of the levels. For example for level 3, with nodes (10,2,6) the average is 6, and the process is the same for each level.
The video example purpose a Deep First Search Approach, so I decided to use the opposite, a Breadth First Search algorithm. Needed to say the optimal solution is to use DFS, but still a good opportunity to show why and play with binary trees just for fun.
The code is available at: https://gist.github.com/djaquels/0d4162aa94ebe012a950c66f1ccddd4a
So when using BFS, we can use a stack (First In, First Out) so we traverse the tree per level.
For example, for Node(4) with leftChild = Node(6), rightChild = None,
We first add 4, the node, value to the corresponding index in the result array, so we can calculate the average later, and we add each one of its nodes to the stack.
For the given example, we would have the following stack, for level 3
This is when using this approach gets tricky and at the same makes DFS the best option.
When empty nodes are present in a level, we have to keep track of these nodes, and add 2 empty nodes more to the stack, this makes the time complexity for this algorithm to pass from O(n) for DFS to O(2**n) (2 to the power of n) [from linear to exponential].
So, although we avoid the use of recursion with BFS, we ended having the worst time complexity.
Regarding Space complexity, we improve a little, by avoiding the use of a hash map, and working directly on the result array, so instead of 0 (levels*nodes) we end with 0 (nodes).
As conclusion, this is a good example that sometimes the "natural" or first intuition approach is not always the best path to follow, being a Breadth Level one may think going for BFS is a good option but in the end DFS improves our time complexity (and perhaps make our code implementation easier too).
Also, In a real interview would be great to compare both approaches as in this post, and mention why one alternative works better than others.
