BST(Binary Search Tree) Testdome in Python

1
votes

I need solution about the problem which is posted in test-dome.

Here is Problem

Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree.

Write a function that, efficiently with respect to time used, checks if a given binary search tree contains a given value.

For example, for the following tree:

n1 (Value: 1, Left: null, Right: null) n2 (Value: 2, Left: n1, Right: n3) n3 (Value: 3, Left: null, Right: null) Call to contains(n2, 3) should return True since a tree with root at n2 contains number 3.

And Following is my answer. I'm programming python.

import collections
Node = collections.namedtuple('Node', ['left', 'right', 'value'])

def contains(root, value):
    if value == root.value:
        return True
    elif value > root.value:
        if root.right != None:
            return contains(root.right, value)
    elif value < root.value:
        if root.left != None:
            return contains(root.right, value)


n1 = Node(value=1, left=None, right=None)
n3 = Node(value=3, left=None, right=None)
n2 = Node(value=2, left=n1, right=n3)

print(contains(n2, 2))

Now, I passed 33.3%, Please help me to pass 100%

2
pythonalgorithmrecursionbinary-search-treenamedtuple
That's cheating! – Bharath

2 Answers

1
votes

You need to check first if root is None, then return False, you don't need to check if root.left is None or root.right is None

Then like the other answer mentioned, your code always looks to right.

If the value you are looking for is less than root's value go to left.

Also you don't need elif because you are returning from the if

With those changes:

def contains(root, value):
    if root is None:
        return False
    if value == root.value:
        return True
    if value > root.value:
        return contains(root.right, value)
    if value < root.value:
        return contains(root.left, value)
1
votes

point 1: you are going right sub-tree always. whether the root value is lower or higher than the key.

point 2: you should go left when the root value is higher than the key.

point 3: you should go right when the root value is lower than the key.

do the following changes in your code: 

if value == root.value:
    return True
elif root.value > value:
    if root.left != None:
        return contains(root.left, value) #going left
elif root.value < value:
    if root.right != None:
         return contains(root.right, value) #going right