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)
contains(n2, 3)should return
Truesince 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?