Find matrix row elements in a binary tree

Question

I am trying to write a function which given a binary search tree T of integers and a rectangular matrix M of integers, verify if there exists a row of M whose values belong to T.
This is my code:

M = [
    [1, 2, 3],
    [4, 5, 6]
    ]

class Tree:
    def __init__(self, root=None, left=None, right=None):
        self.root = root
        self.left = left
        self.rigth = right

def FindRowInTree(T, M):
    if T is None:
        return False
    else:
        for r in M:
            for e in r:
                if e == T.root and FindRowInTree(T.left, M) is True and FindRowInTree(T.right, M) is True:
                    return True
                FindRowInTree(T.left, M) and FindRowInTree(T.right,M)
        return False

t = Tree(4, Tree(5, None, None), Tree(6, None, None))
x = FindRowInTree(t, M)
print(x)

It always returns False.

What would I need to change to make it work properly?

Answer 1

Break the problem into pieces. First write a function to find a single value in the tree:

class Tree:
    def __init__(self, root=None, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

    def __contains__(self, value):
        return (
            self.root == value
            or self.left is not None and value in self.left
            or self.right is not None and value in self.right
        )

Note that with an ordered binary tree, you could make this function more efficient by having it only check left or right depending on how the value you're looking for compares to the root value; that's what a "binary search" is. Since your tree is unordered, though, you just need to search both children at each node, meaning you're traversing the entire tree.

In any case, once you have a function that looks up a single value, all you need to do is call it in a loop:

def find_row_in_tree(tree, matrix):
    return any(
        all(i in tree for i in row)
        for row in matrix
    )

If you're trying to do this in a more efficient way, an unordered binary tree is not doing you any favors; I'd just write a utility function to convert it to something more useful, like a set:

def tree_to_set(tree):
    if tree is None:
        return set()
    return {tree.root} | tree_to_set(tree.left) | tree_to_set(tree.right)

def find_row_in_tree(tree, matrix):
    tree_as_set = tree_to_set(tree)
    return any(tree_as_set.issuperset(row) for row in matrix)