Skip to content
Code it · Write it

Insert into a binary search tree

Write insert(root, val) (Python, JavaScript and TypeScript). root is a TreeNode with val, left and right (None/null where there is no child), or None/null for an empty tree. The tree is a binary search tree: smaller values to the left of a node, larger to the right.

Add a new TreeNode(val) (new TreeNode(val) in JavaScript) where it belongs, and return the root. val is never already in the tree.

From the root, go left when val is smaller than the node’s value and right otherwise, until there is no child that way. Recursion makes the linking easy: the call on an empty spot returns the new node, and each caller stores what came back as its child.

def insert(root, val):
    # root is a binary search tree, or None when it is empty.
    # Add TreeNode(val) where it belongs, and return the root.
    return root