Mirror/Deep copy of a Binary Tree/BST without recursion (iterative approach)

dc_bst.py

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: The root of binary tree
    @return: root of new tree
    """
    def cloneTree(self, root):
        # write your code here
        if root is None:
            return None
        
        oriq = [root]
        res = TreeNode(root.val)
        newq = [res]
        
        while len(newq) > 0:
            new = newq.pop()
            ori = oriq.pop()
            
            new_left = None
            new_right = None
            if ori.left is not None:
                new_left = TreeNode(ori.left.val)
                new.left = new_left
                oriq.insert(0, ori.left)
                newq.insert(0, new_left)
            if ori.right is not None:
                new_right = TreeNode(ori.right.val)
                new.right = new_right
                oriq.insert(0, ori.right)
                newq.insert(0, new_right)
        
        return res