-1
\$\begingroup\$

I am working on a python3.6.5 question about BST:

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.

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 a 33% score. 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?

\$\endgroup\$

closed as off-topic by 200_success, l0b0, dfhwze, Mast, Toby Speight Aug 14 at 7:00

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – 200_success, l0b0, dfhwze, Mast, Toby Speight
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ Your question is off-topic for Code Review, because the result is only 33% correct. Our rules require that the code work correctly before we can review it. See the help center. \$\endgroup\$ – 200_success Aug 14 at 5:37
  • 2
    \$\begingroup\$ Note that your function never returns False. (It can sometimes return None.) \$\endgroup\$ – 200_success Aug 14 at 5:37
  • \$\begingroup\$ Does the website give any comments or feedback? Or just a score of 33%? Perhaps they want an iterative solution instead of a recursive one. \$\endgroup\$ – RootTwo Aug 14 at 6:41
  • 1
    \$\begingroup\$ What does a score of 33% mean, that it fails some of the test cases? If that's so, your code is not ready for review yet. \$\endgroup\$ – Mast Aug 14 at 6:49
-1
\$\begingroup\$

Like @200_success pointed out in the comments, your function will never return False. Try to follow the function code in this case: what if you arrive to a node that has no left/right nodes? You will arrive at the end of the function, where there is no return statement. Adding a return False there gives me 100% score.

As a recommendation, instead of nesting to ifs you can use the and operator to chain conditions. Also, to check if something is (not) None, it's better to use x is not None:

if value > root.value and root.right is not None:
    return contains(root.right, value)

elif root.left is not None:
    return contains(root.left, value)

else:
    return False
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.