Tree: Finding Largest Value in each row of binary tree BFS Python

PHOTO EMBED

Wed Aug 03 2022 20:16:32 GMT+0000 (UTC)

Saved by @bryantirawan #python #methods #queue #codesignal #breath #first #search #max

#
# Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
import math 
def solution(t):
    if t is None: return [] 
    
    stack = [t] 
    result = []
    
    while len(stack) > 0: 
        result.append(max(tree.value for tree in stack)) 
        next_row = [tree.left for tree in stack if tree.left] + [tree.right for tree in stack if tree.right]
        stack = next_row 
    return result 


 #1. Add max value of ‘stack’ to result. 2. Create a new list of all next values for each value in stack. 3. redefine stack to this newly made list. 4. repeat 


#alternate solution 
def solution(t):
    largestValues = []
    q = []
    height = 0
    if t:
        q.append([t, height])
        while q:
            item = q.pop()
            node = item[0]
            currentHeight = item[1]
            if node.left:
                q.insert(0, [node.left, currentHeight + 1] )
            if node.right:
                q.insert(0, [node.right, currentHeight + 1])
            checkLargest(node.value, currentHeight, largestValues)
            
    return largestValues
    
        
def checkLargest(value, height, largestValues):
    if height == len(largestValues):
        largestValues.append(value)
    else:
        if largestValues[height] < value:
            largestValues[height] = value
content_copyCOPY

codesignal