How to search in a tree?

Question

I have this follow tree implementation:

class Node:
    def __init__(self, *, val):
        self.val = val

    def __repr__(self):
        return "{}(val={})".format(type(self).__name__, self.val)


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

    def __repr__(self):
        return "{}(val={}, left={}, right={})".format(type(self).__name__, self.val, self.left, self.right)

Now I try to add a method that checks if a element exists:

def exists(self, val):
    if self.val == val:
        return True
    return self.left.exists(val) or self.right.exists(val)

Then if I try to search 1, it's fine. But with 2, It errors out.

Traceback (most recent call last):
  File "...", line 30, in <module>
    print(tree.exists(2))
  File "...", line 20, in exists
    return self.left.exists(val) or self.right.exists(val)
  File "...", line 20, in exists
    return self.left.exists(val) or self.right.exists(val)
AttributeError: 'Node' object has no attribute 'exists'

For reference, here's the tree I made:

tree = Tree(val=1,
            left=Tree(val=Node(val=2), left=Node(val=3), right=Node(val=4)),
            right=Tree(val=Node(val=2), left=Node(val=3), right=Node(val=4)))

How can I recursively search in a tree?

Answer 1

Just jettison the Node class which serves no purpose whatsoever:

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

    def exists(self, val):
        if self.val == val:
            return True
        if self.left and self.left.exists(val):
            return True
        if self.right and self.right.exists(val):
            return True
        return False 

tree = Tree(val=1,
            left=Tree(val=2, left=Tree(val=3), right=Tree(val=4)),
            right=Tree(val=2, left=Tree(val=3), right=Tree(val=4)))