How to search in a tree?

user_15434706 0
Viewed 46

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?

recursive-datastructures binary-tree tree search python
3 Answers

The bottom of you recursion is not only if you found the value (if self.val == val) but also if you reach a leaf of your tree (if self.isLeaf return false)

user_173966230

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)))
user_23901820

The error says "Node" doesn't have a method "exists" which is correct. You didn't write Node's version of "exists." You need to work out what data and method belong to each node, and what data and methods should be on the tree as a whole.

But additionally, you can't look at left or right without checking to see if they are None.

self.left.exists()

should be replaced with

self.left and self.left.exists()

And the same for right

user_17665440
Related