---

from collections import deque
class Node:
    def __init__(self, val):
        self.val=val
        self.chids = []
def bfs(root: Node):
    if not root:
        return None
    res = []
    deq = deque([root])
    while deq:
        el = deq[0]
        if el.left:
            deq.append(el.left)
        if el.right:
                deq.append(el.right)
        deq.pop.left()
    return res

def dfs(root):
     if not root:
          return[]
     return dfs(root.left)+[root.val]+dfs(root.right)
          

root = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node9 = Node(9)
root.left = node2
root.right= node3
root.left = node4
root.right = node6
root.left = node9
root.right = node5