```#
# 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```
```# //Tree Traversal (visit every node once)
# //Heavy on recursion

# //Breadth-first (BFS) vs. Depth-first (DFS)

# // DFS:
# // 1) in order (go in order of value)
# // 2) pre order (start at root)
# // 3) post order (start at botom)

# //When to use BFS vs. DFS:
# //For a fully loaded (wide) tree, BFS queue will be overloaded in the start (overloaded space complexity)
# //For a longer tree, DFS will take more memory (more rare, Trees are usually wide)
# //Big O for both is same

# //In order: useful if you want sorted array at end (you don't really know what the root is bc it's in the middle)
# //PreOrder: useful to "export a tree" so that it can be copied bc it flattens it

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

class BinarySearchTree:
def __init__(self):
self.root = None

def insert(self, value):
#creates new Node
new_node = Node(value)
#start at root
#if no root exists, root becomes new_node
if self.root == None:
self.root = new_node
return self

current = self.root

while True:
#to handle special case where value is same as current node
#you can return None or you can add a counter property
if value == current.value:
return None
#check to see if value is less than current
if value < current.value:
#check to see if there is node to left
#if not, add new_node to left
if current.left == None:
current.left = new_node
return self
#if there is node to left, move to that node and repeat
current = current.left
#check to see if value is greater than current
else:
#check to see if there is node to right
#if not, add new_node to right
if current.right == None:
current.right = new_node
return self
#if there is node to right, move to that node and repeat
current = current.right

#Breadth first search iterative using queue
def BFS(self):
node = self.root
#we will return data
data = []
queue = []
#place root node inside queue (recall FIFO)
queue.append(node)
#while queue is not empty
while len(queue) > 0:
#dequeue node from queue and append to data
node = queue.pop(0)
data.append(node)
#if there is left on node dequeued, add to queue
if node.left:
queue.append(node.left)
#if there is right on node dequeued, add to queue
if node.right:
queue.append(node.right)
#above two lines of code could be changed if it was a ternary tree, etc. instead of binary
#just loop for all children
return data

#parent down uses recursive
def DFSPreoder(self):
data = []
#if you want to DFS not from root, create a variable here named current and specify which node to start from
#helper function
def traverse(node):
#all of root node's left will happen first, then right
#for other types of DFS, just tweak this order
data.append(node.value)
if node.left:
traverse(node.left)
if node.right:
traverse(node.right)

traverse(self.root)
return data

#children up, root should be last value
def DFSPostOrder(self):
data = []

def traverse(node):
if node.left:
traverse(node.left)
if node.right:
traverse(node.right)
data.append(node.value)

traverse(self.root)
return data

#result data list should be sorted
def DFSInOrder(self):
data = []
def traverse(node):
if node.left:
traverse(node.left)
data.push(node.value)
if node.right:
traverse(node.right)
traverse(self.root)
return data

t = BinarySearchTree()
t.insert(1)
t.insert(5)
t.insert(6)
t.insert(2)
t.insert(0)
t.insert(-1)
t.insert(7)

print(t.DFSInOrder())```