findHeightBinTree.py

# Ref: https://www.freecodecamp.org/news/how-to-calculate-a-binary-trees-height-using-array-iteration-in-ruby-63551c6c65fe/
# and https://helloacm.com/comparing-left-and-right-branch-of-a-complete-binary-tree/

# How do we know how tall a binary tree is when it’s already in array form(BFS flattened array form)?

def solution(arr):
    # Type your solution here 
    # in a list like this one, a node's left and right children are present at 2*i+1 and 2*i-1th indexes respectively
    if not arr:
        return ""
    
    if len(arr) == 0:
        return 0
    
    def sum(arr,index):
        if (index - 1) < len(arr): # terminating condition
            if arr[index - 1] == -1: return 0    #non existant node
            return arr[index-1] + sum(arr,(index*2)) + sum(arr, index*2+1)
        return 0 
    
    left = sum(arr, 2)
    right = sum(arr, 3)
    print(left, right)
    return "" if left == right else "Right" if right > left else "Left"
    
    
tc1 = [3, 6, 2, 9, -1, 10] # "Left" 
tc2 = [1, 4, 100, 5] # "Right"
tc3 = [1, 10, 5, 1, 0, 6] # "" - Equal branches
tc4 = [] # "" - Empty tree
tc5 =  [1] # "" - only root node

for i in [tc1, tc2, tc3,tc4,tc5]:
    print(solution(i))