variable scope and referencing-CodePudding

Here, I have copied a reference to the "root" to the "temp" variable before performing operation on root variable on a Binary Search Tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        temp = root
        prev_node = None
        while True:
            if not root:
                if prev_node is None:
                    root = TreeNode(val)
                elif val > prev_node.val:
                    prev_node.right = TreeNode(val)
                else:
                    prev_node.left = TreeNode(val)
                break
            elif val > root.val:
                prev_node = root
                root = root.right
            elif val < root.val:
                prev_node = root
                root = root.left
        return temp

This approach works for almost all testcases but fails for when root = []

At this point I realized there is something wrong going on with variable scope, so I started debugging and changed my code to as shown below:

    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        temp = root
        prev_node = None
        while True:
            if not root:
                if prev_node is None:
                    temp = TreeNode(val)
                elif val > prev_node.val:
                    prev_node.right = TreeNode(val)
                else:
                    prev_node.left = TreeNode(val)
                break
            elif val > root.val:
                prev_node = root
                root = root.right
            elif val < root.val:
                prev_node = root
                root = root.left
        return temp

Now, second piece of code works perfectly, but even after debugging it line by line I could not understand what exactly went wrong with my first piece of code. I have a vague idea that it was related to the variable scope, but just can't put my finger on it. Any help is appreciated.

CodePudding user response：

There are only really three lines executed in case root is []:

temp = root
    ...
    if not root:
        if prev_node is None:
            root = TreeNode(val)
    ...
return temp

So, yeah. temp is set to [], then root is set to a TreeNode (which doesn't affect temp), then temp (which is still []) is returned.