Easy Recursive Descent Trees
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 root