Alternative Solution For Meta/Facebook Code Practice Example https://www.facebookrecruiting.com/profile/preparation_hub

MetaCodePractice.py

#https://www.facebookrecruiting.com/profile/preparation_hub
"""
   4
 /   \
 2    8
/ \  / \
3  N 6  9
           \
N N N N N N  N  7

avgs = []
root = 4
l = 0
avgs = [4]
l = 1
2,8 => 5
avgs = [4,10]

T = O(2**n)
S = O(n)
"""

import math

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None



# bfs -> 4 , 2 8 , 3 6 9 ,
# r: 4
# q: 2 8
# r: 2
# q: 8 3 None
# r: 8
# q: 3 None 6 9
# r: 3
# q: None 6 9 None None
# r: None
# q: 6 9  None None
# r: 6
# q: 9 None None None None
# r: 9
# q: None None None None 7 None

# Build test case
''' root = Node(4)
root.left = Node(2)
root.right = Node(8)
root.left.left = Node(3)
root.right.left = Node(6)
root.right.right = Node(9)
root.right.right.right = Node(7) '''

root =  Node(4)
root.left = Node(7)
root.right = Node(8)
root.left.left = Node(10)
root.left.right = Node(2)
root.right.right = Node(6)
root.left.right.right = Node(6)
root.left.right.right.left = Node(2)

# Test Function
def test_f(expected,testCase):
    if len(expected) != len(testCase):
        return False
    for i in range(0,len(expected)):
        if expected[i] != testCase[i]:
            return False
    return True

# Implementation
def averages(root):
    avgs = []
    h = 6
    if root is None:
        return avgs
    level = 0
    counter = 1
    queue = [root]
    avgs = [[]]
    nulls = 0
    while len(queue) > 0:
        #print(avgs)
        current = queue.pop()
        if current is None:
            if counter == 1:
                level += 1
                counter = 2**level
                avgs.append([])
            counter -= 1
            nulls += 1
            continue
        if counter > 1:
            #print("dormamo")
            avgs[level].append(current.value)
            counter -= 1
        else:
            #print(avgs,level,current.value,counter)
            avgs[level].append(current.value)
            level += 1
            counter = 2**level
            avgs.append([])
            for n in range(nulls):
                queue.insert(0,None)
                queue.insert(0,None)
            nulls = 0
        queue.insert(0,current.left)
        queue.insert(0,current.right)
    #print(avgs)
    return list(map(lambda lev: int(math.ceil(sum(lev)/len(lev))), avgs  ))


# Execution
#expected = [4,5,6,7]
expected = [4,8,6,6,2]
test = averages(root)
print(test)
assert test_f(expected,test),"Test Failed {} {}".format(test,expected)