Foundation drill for this topic
Easy Recursive Descent
In plain English: Add a new value to a binary search tree so that the BST property is preserved.
BST property guides you left or right at each node — the first None you reach is where the new node belongs.
Prompt
Insert a value into a binary search tree.
Try to write it from scratch before scrolling down.
Solution
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bst_insert(root, val):
if root is None: # None = empty slot, insert here
return TreeNode(val)
if val < root.val:
root.left = bst_insert(root.left, val)
else:
root.right = bst_insert(root.right, val)
return rootQuick recall drills to reinforce this pattern.
Search for the insertion point, create new node there. Always inserts as a leaf. O(h) time.
def insertIntoBST(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insertIntoBST(root.left, val)
else:
root.right = insertIntoBST(root.right, val)
return root
# Iterative:
def insertIntoBST_iter(root, val):
node = TreeNode(val)
if not root: return node
cur = root
while True:
if val < cur.val:
if not cur.left: cur.left = node; break
cur = cur.left
else:
if not cur.right: cur.right = node; break
cur = cur.right
return rootBST property: if both targets < root go left, both > root go right, otherwise root is LCA. O(h) time.
def lowestCommonAncestor(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return rootThe TreeNode class is the foundation for all binary tree problems. Must be instant.
class TreeNode:
def __init__(self, val, l=None, r=None):
self.val = val
self.left = l
self.right = r