Largest Binary Search Tree Value
I am trying to find the largest value in a binary search tree. An example solution is given below, but I am trying to figure out if there is something wrong with my solution? My problem with the sample solution is that it seems that each node is not None twice: once in "if not current.right" and the second in "while current ... current = current.right" which seems redundant.
Solution example:
def find_largest(root_node):
current = root_node
while current:
if not current.right:
return current.value
current = current.right
My decision:
def find_largest(root_node):
current = root_node
if current:
while current.right is not None:
current = current.right
return current.value
Question / code source: Interviewcake.com
source to share
Your analysis is correct, the sample solution checks None
twice per node and your solution only checks once, otherwise they are equivalent. Id also says that your solution is more readable, but this is somewhat subjective.
As an improvement, you can get rid of the first line in the body of your function by calling the function argument current
instead root_node
. This gives you the added benefit that now the argument name does not imply that your function can only be called with the root node as an argument. Indeed, it correctly finds the largest value in any subtree.
source to share