CODEWITHSUNDEEP
python-3.xbinary-search-tree
ywan
ywan

Reputation: 137

Is there any way to improve my py3 code for a binary search tree question?

I am working on a python3 question about BST from https://www.testdome.com/questions/python/binary-search-tree/24973?visibility=1&skillId=9:

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:

Call to contains(n2, 3) should return True since a tree with root at n2 contains number 3.

My code is:

import collections

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

def contains(root, value):
    if value == root.value:
        return True

    if value > root.value:
        if root.right != None:
            return contains(root.right, value)
    else:
        if root.left != None:
            return contains(root.left, 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, 3))

It can work but the website only gave me 33 scores. I found some similar questions, but they are based on c++. I want to know is there any way to improve my code to get a better score based on python3?

Thank you!!

Upvotes: 1

Views: 216

Answers (1)

Shihab Shahriar Khan
Shihab Shahriar Khan

Reputation: 5455

Well your code never returns False, so python automatically returns a None instead. Just adding a return False at the very last line of contains function would suffice. 

def contains(root, value):
    if value == root.value:
        return True

    if value > root.value:
        if root.right != None:
            return contains(root.right, value)
    else:
        if root.left != None:
            return contains(root.left, value)
    return False

Upvotes: 1

Related Questions