DSA sheet · Trees · BST pattern

Insert into a Binary Search Tree

This problem joins the two before it. From Search in a BST we take the walk: compare, then go left or right, one path only. From Sorted Array to BST we take the building habit: assign what a call returns to root.left / root.right, and always return the node. The key insight: a new value always goes into the empty (None) spot where a search for it would end. The teacher shows a recursive solution and then an iterative one with O(1) extra space.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (the BST rule)
• Part A · Insert with recursion (DFS)
• Part B · Insert with a loop (iterative, O(1) space)
• Part C · Revision page

Part 0 · Before starting

What is a tree node?

Each node has a value, a left child link and a right child link. A missing child is None. A leaf is a node with no children.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # the number in this node
        self.left = left     # left child, or None
        self.right = right   # right child, or None

The BST rule

The rule is about the whole subtree, not just the children. A node deep down must respect every ancestor above it. Example: in the tree below, 3 is the right child of 2, so 3 > 2. But 3 also sits in 4's left subtree, so it must be < 4 as well. It is, so the tree is fine.

          4
        /   \
       2     7
      / \
     1   3

After we insert, the tree must still follow this rule everywhere. That's the whole challenge.

Inorder of a BST is sorted

Inorder = left subtree, node, right subtree. Since the left side is all smaller and the right side all bigger at every node, inorder lists the values in increasing order: the tree above gives 1 2 3 4 7. An easy way to check our insert worked: the new inorder should be the old sorted list with the new number slotted into its place.

Height

The height h is the number of levels (nodes on the longest root-to-leaf path). We use it for the complexity.

Part A · Insert with recursion (DFS)

LeetCode 701 · Insert into a Binary Search Tree

1The question in simple words

You get the root of a BST and a number val. Put a new node with value val into the tree so that it is still a BST, and return the root.

        4
      /   \
     2     7
    / \
   1   3

        4
      /   \
     2     7
    / \   /
   1   3 5

        4
      /   \
     2     7
    / \     \
   1   3     8

LeetCode accepts any valid BST. The simple answer, and the one the teacher builds, adds the new value as a new leaf and doesn't move any old node.

2What the constraints tell us

• Number of nodes: 0 to 10⁴ → 0 is allowed, so the tree can be empty (root is None). Then the answer is a tree with one node: val. E.g. empty tree + insert 5 → just 5. We need this case in the code.
• n up to 10⁴ → an O(n²) idea would be about 10⁸ steps. Around 10⁸ is the edge, and beyond it you risk TLE (Time Limit Exceeded). Our solution will be much faster anyway.
• Values from −10⁸ to 10⁸ → close to the int limit (about 10⁹) in Java/C++, but still safe, because we only compare values. Overflow is only a worry when you add or multiply big numbers.
• "It is guaranteed that val does not exist in the original BST." → at every node, val is either bigger or smaller, never equal. So we always have a direction to go, and we never have to decide what to do with duplicates.

3Intuition: how to think about it

Pretend you are searching for val. Since it's not in the tree, the search must fail: it keeps choosing left or right until it steps onto an empty spot (None). That empty spot is exactly where val belongs. Every comparison on the way down made sure the spot is on the correct side of every ancestor, so placing it there keeps the BST rule true everywhere.

So: walk down like search → when you hit None, put the new node there → make sure the parent gets linked to it.

4Building the conditions from examples

Example: insert 5. Where do we end up?

• At 4: is 4 bigger than 5? No → 5 must go to the right of 4. Move to 7.
• At 7: is 7 bigger than 5? Yes → 5 must go to the left of 7. Move to 7's left… which is None.

We landed on None. Is that an error? Try another value. Insert 8: 4 → right → 7 → right → None again. Since val is never in the tree, every insert ends at a None. So None is not a failure, it's the target.

Rule 1 (base case): reached None → create the node and return it

In Search, reaching None meant "return None, not found". Here it means the opposite: build the new node right here and return it. The teacher's tip: for recursion, always think of the base case first.

Rule 2: decide the side, and attach what comes back

• root.val < val (node smaller than val, like 4 < 5) → val belongs on the right → recurse on root.right.
• otherwise (node bigger, like 7 > 5) → val belongs on the left → recurse on root.left.

But this time we must store the result: root.left = self.insertIntoBST(root.left, val). Why? When the call on 7's left reaches None, it creates node 5 and returns it. Somebody has to hook 5 under 7. The call for 7 does that by writing the result into root.left.

Rule 3: return root (the extra line that saves the tree)

After 5 is attached under 7, the call for 7 ends. But remember how 7 was reached: the call for 4 did root.right = self.insertIntoBST(7, 5). Whatever the call for 7 returns will be written into 4.right.

• Should 4.right change? No. 7 was already there and is still the right child of 4. So the call for 7 must return 7 itself, which is root.
• If we forget return root, Python returns None by default. Then 4.right becomes None, and the whole 7-subtree (with the new 5) disappears.

  forgot "return root":     4
                          /   \
                         2    None   ← 7 and 5 are lost
                        / \
                       1   3

5Approach steps

1. If root is None → return a new node with val.
2. If root.val < val → root.right = insert(root.right, val).
3. Else → root.left = insert(root.left, val).
4. Return root.

6Code (Python)

class Solution:
    def insertIntoBST(self, root, val):
        if root is None:                     # empty spot found -> new node lives here
            return TreeNode(val)
        if root.val < val:                   # val is bigger -> belongs on the right
            root.right = self.insertIntoBST(root.right, val)
        else:                                # val is smaller -> belongs on the left
            root.left = self.insertIntoBST(root.left, val)
        return root                          # give the parent its same child back

7Code line by line

8Dry run using the call stack

Insert 5 into 4 → (2 → (1, 3), 7). ins(x) means the call with root = x.

1. ins(4): not None. 4 < 5 → go right: it will run 4.right = ins(7). (ins(4) waits.)
2. ins(7): not None. 7 < 5? No → else → it will run 7.left = ins(None). (ins(7) waits.)
3. ins(None): empty spot → create node 5 and return it.
4. Back in ins(7): 7.left = 5 → 5 is now connected. ins(7) returns 7.
5. Back in ins(4): 4.right = 7 (the same as before, nothing lost). ins(4) returns 4, the root. Done ✓

Insert 8 instead: ins(4) → right → ins(7): 7 < 8 → right → ins(None) creates 8 → 7.right = 8 → return 7 → 4.right = 7 → return 4 ✓

Check: the inorder after inserting 5 is 1 2 3 4 5 7, still sorted ✓

9Complexity & remember

• Time O(h): at every level we look at just one node and pick a side, exactly like search. The teacher says O(log n), which is true for a balanced tree (log n levels).
• Space O(h): one waiting call per level on the stack, so O(log n) when balanced.

Part B · Insert with a loop (iterative)

1The question

Same question. The teacher's follow-up: the recursive code is already fast, but what if an interviewer wants it without the O(h) stack space, in constant space? Then we drop recursion and walk down with a pointer, as in the iterative Search.

2Constraints

Same as Part A. The 0-node case now needs its own check before the loop, because there's no base case that handles it automatically.

3Intuition

Walk down the tree with one finger, choosing left or right at each node. But don't step onto the None. Stop one step before it, while you're still on the parent, because that's the only way to attach the new node: parent.left = new or parent.right = new.

4Building the conditions

Empty tree first

If root is None, there's nothing to walk. Return TreeNode(val) straight away.

Why a separate pointer cur?

At the end we must return the top of the tree (4). If we moved root itself down the tree, we'd lose track of the top. So we keep root fixed and walk with a copy: cur = root.

Look before you step

• If val > cur.val, we want to go right. Before moving, check cur.right:
  • it's None → this is the empty spot. Do cur.right = TreeNode(val) and break out of the loop (the job is done).
  • it's a node → step there: cur = cur.right.
• Else (val is smaller) → the same thing on the left: if cur.left is None, attach there and break, otherwise cur = cur.left.

After the loop

Return root, the untouched top. We've only added one leaf somewhere below.

5Approach steps

1. If root is None → return TreeNode(val).
2. cur = root.
3. Loop: if val > cur.val → if cur.right is None, attach there and stop. Otherwise move right.
4. Else → if cur.left is None, attach there and stop. Otherwise move left.
5. Return root.

6Code (Python)

class Solution:
    def insertIntoBST(self, root, val):
        if root is None:                      # empty tree -> new node is the tree
            return TreeNode(val)
        cur = root                            # walk with a copy, keep root safe
        while True:
            if val > cur.val:                 # belongs on the right
                if cur.right is None:         # empty spot -> attach and stop
                    cur.right = TreeNode(val)
                    break
                cur = cur.right
            else:                             # belongs on the left
                if cur.left is None:
                    cur.left = TreeNode(val)
                    break
                cur = cur.left
        return root

7Code line by line

8Dry run (hand table)

Insert 5 into 4 → (2 → (1, 3), 7).

Insert 8: round 1: 8 > 4 → 4.right is 7 → cur = 7. Round 2: 8 > 7 → 7.right is None → attach 8 there, break → return 4 ✓

Empty tree, insert 5: the first if returns a single node 5 ✓

9Complexity & remember

• Time O(h): still one node per level. O(log n) balanced, O(n) for a straight-line tree. Creating the node itself is O(1).
• Space O(1): just cur. No extra data structure, no call stack. (The one new node is the answer, not extra space.)

Part C · Revision page

def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

s = Solution()
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
root = s.insertIntoBST(root, 5)
print(root.right.left.val)           # 5  (left child of 7)
root = s.insertIntoBST(root, 8)
print(root.right.right.val)          # 8  (right child of 7)
print(inorder(root))                 # [1, 2, 3, 4, 5, 7, 8]
print(s.insertIntoBST(None, 5).val)  # 5  (empty tree)

Based on this video: Insert into a Binary Search Tree