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

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

#
# 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