A breadth-first search implementation in Python 3 based on sample code in https://medium.com/basecs/breaking-down-breadth-first-search-cebe696709d9. Sample output: https://imgur.com/a/ZdRlasW

bfs.py

#!/usr/bin/env python3

from ete3 import Tree
from random import randint

def level_order_search(root_node, to_find = None):
    if root_node is None:
        return

    queue = []
    queue.insert(0, root_node)

    while len(queue) > 0:
        current_node = queue.pop()

        if current_node.left is not None:
            queue.insert(0, current_node.left)

        if current_node.right is not None:
            queue.insert(0, current_node.right)
        
        if current_node is root_node:
            print(current_node.value, end=" ") 
        else:
            print("-> {}".format(current_node.value), end=" ")
        
        if to_find is not None and current_node.value == to_find:
            print()
            print("We found it!")
            return
    
    print()
    if to_find is not None:
        print("{} isn't in this tree!".format(to_find))

def build_tree(nodes = 0, max_val = 10):
    if nodes == 0: 
        return
    node = Node(randint(0, max_val))
    nodes -= 1
    node.set_left(build_tree(nodes // 2 + nodes % 2))
    node.set_right(build_tree(nodes // 2))
    return node

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

    def __str__(self):
        return "value: {}, left: {}, right: {}".format(self.value, repr(self.left), repr(self.right))
    
    def __repr__(self):
        return "Node({}, {}, {})".format(self.value, repr(self.left), repr(self.right))

    def set_left(self, left):
        self.left = left if (isinstance(left, Node) or left is None) else Node(left)
    
    def set_right(self, right):
        self.right = right if (isinstance(right, Node) or right is None) else Node(right)

    def pretty_print(self, topLevel = True):
        output = ""
        hasRight = False
        hasLeft = False

        if self.right is not None:
            hasRight = True
            output += "(" 
            output += self.right.pretty_print(False)
        
        if self.left is not None:
            hasLeft = True
            if hasRight:
                output += ","
            else:
                output += "("
            output += self.left.pretty_print(False)
        
        if hasRight or hasLeft:
            output += ")"
        
        output += str(self.value)

        if not topLevel:
            return output
        
        t = Tree(output + ";", format=1)
        print(t.get_ascii())
        print()

if __name__ == "__main__":
    root = build_tree(15, 20)
    root.pretty_print()
    level_order_search(root, 5)