CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-tree
Swa1n Suen
Swa1n Suen

Reputation: 133

Is it possible to use one pointer to insert a node into a BST?

I wonder if I can insert without the trailing pointer y. Here is my code:

def tree_insert(root, key):
    z = TreeNode(key)
    y = None
    x = root
    while x:
        y = x
        if z.val < x.val:
            x = x.left
        else:
            x = x.right
    if y is None:
        root = z
    elif z.val < y.val:
        y.left = z
    else:
        y.right = z

Thank you!

Upvotes: 0

Views: 78

Answers (1)

trincot
trincot

Reputation: 350137

Your function has an issue: when the function assigns root = x, then the caller will not know about it, since root is a local variable.

You can solve this in many ways. One is that you have a contract that the function always returns the root.

To avoid an y you can just assign z as soon as you know where it should go:

def tree_insert(root, key):
    z = TreeNode(key)
    if not root:
        return z  # new root
    x = root
    while True:
        if z.val < x.val:
            if not x.left:
                x.left = z
                return root
            x = x.left
        else:
            if not x.right:
                x.right = z
                return root
            x = x.right

So use it as follows -- always assigning back to root:

root = None
root = tree_insert(root, 5)
root = tree_insert(root, 2)
root = tree_insert(root, 4)
root = tree_insert(root, 8)
root = tree_insert(root, 1)

You can even save more variables, if you turn the function into a recursive one:

def tree_insert(root, key):
    if not root:
        return TreeNode(key)
    if key < root.val:
        root.left = tree_insert(root.left, key)
    else:
        root.right = tree_insert(root.right, key)
    return root

Again, this function returns the root, and the caller must take it into account.

Upvotes: 1

Related Questions