Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a binary search tree root and an integer val, determine whether val is in the tree.
Constraints
n ≤ 100,000 where n is the number of nodes in root
Linear Algorithm to Search in a Binary Search Tree
We can perform a linear algorithm to traverse all nodes in the Binary Search Tree. Complexity is O(N), and the space complexity is O(N) due to implicitly using Stack from Recursion:
1 2 3 4 5 6 7 8 9 10 11 12 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def searchInBST(self, root, val): if root is None: return False if val == root.val: return True return self.searchInBST(root.left, val) or self.searchInBST(root.right, val) |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def searchInBST(self, root, val):
if root is None:
return False
if val == root.val:
return True
return self.searchInBST(root.left, val) or self.searchInBST(root.right, val)Logarithm Algorithm to Search in a Binary Search Tree
Since the Tree is Binary Search Tree, we can cut off a branch everytime when the value is not equal to the current node. When the value is larger, we know it is somewhere in the right tree, otherwise, it must be in the left tree where the nodes are always smaller.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def searchInBST(self, root, val): if root is None: return False if val == root.val: return True if val < root.val: return self.searchInBST(root.left, val) return self.searchInBST(root.right, val) |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def searchInBST(self, root, val):
if root is None:
return False
if val == root.val:
return True
if val < root.val:
return self.searchInBST(root.left, val)
return self.searchInBST(root.right, val)If the Binary Search Tree is highly balanced, the complexity to search a node in a BST is O(LogN). A degenerated Binary Search Tree could be a singly linked list as well, and in the worst case, the complexity is O(N).
As this approach is still based on Recursion, O(N) space is required. However, we can easily turn it into iterative algorithm – which requires O(1) constant space by updating the current “root” Node depending on the value comparison:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def searchInBST(self, root, val): while root: if root.val == val: return True if root.val < val: root = root.right else: root = root.left return False |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def searchInBST(self, root, val):
while root:
if root.val == val:
return True
if root.val < val:
root = root.right
else:
root = root.left
return False–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Algorithms to Compute the Difference of Two Maps
Next Post: Algorithm to Maximize Social Distancing
