How can I make a copy of a tuple containing nested tuples in Python?

Question

I'm working on a question that requires me to define a function copy_tree that takes an argument tree (tuple that may contain tuples) and return a copy of the tree (ie. stored in a different memory location).

My current code is:

def copy_tree(tree):
    new_tree = ()
    for i in tree:
        new_i = (i,) + ()
        new_tree = new_tree + new_i
    return new_tree

However, this does not work for the nested tuples, as the tuples inside are not "copied" but rather referred to.

e.g. if I run

a = ((3, 2), 1, (4,), 5)
b = copy_tree(a)
print(a[0] is b[0])

the output has to be False.

How do I make the tuples copies?

Edit: I am not allowed to use the deepcopy module.

Answer 1

Your code is missing the recursive step - you only copy the top-level tuple.

def copy_tree(tree):
  new_tree = ()
  for i in tree:
    # i is not copied
    new_i = (i,) + ()
    new_tree = new_tree + new_i
  return new_tree

Adding recursion produces copies of every layer of the tree. Note that you may copy only tuples:

def copy_tree(tree):
  new_tree = ()
  for i in tree:
    # recursively copy i *if it is a tuple*
    if isinstance(i, tuple):
      new_i = (copy_tree(i),)
    else:
      new_i = (i,)
    new_tree = new_tree + new_i
  return new_tree

---

Recursion fixes the result, but the approach you have taken is inefficient - there are many transient tuples created and thrown away. Every time a tuple is "extended" via +, the old one is thrown away and a new one created.

A first step is to delay creation of the tuple until all children are converted:

def copy_tree(tree):
    children = []
    for child in tree:
        # we *always* preserve a child, so ternary if expresses this better
        child = copy_tree(child) if isinstance(child, tuple) else child
        children.append(child)
    # create a new tuple including all children
    return tuple(children)

Since that list only exists to be turned into a tuple, we can get rid of that as well: a generator expression allows to feed the converted children directly to the tuple constructor.

def copy_tree(tree):
    # generator expression - only run when consumed by tuple later on
    children = (
        copy_tree(child) if isinstance(child, tuple) else child
        for child in tree
    )
    return tuple(children)

Of course, you can also directly put the generator expression inside the tuple.

Answer 2

Here's a simple version that copies the tree by feeding the tuple constructor with a recursive generator. To test it, I've written another recursive function compare_trees, which you can use to check that corresponding tuples aren't identical (using is), and that corresponding inner items have the same value (using ==).

def copy_tree(tree):
    return tuple(copy_tree(u) if isinstance(u, tuple) else u for u in tree)

def compare_trees(tree1, tree2, indent=''):
    print(indent, 'tree1', tree1, 'tree2', tree2, 'identical', tree1 is tree2)
    indent += '  '
    for u1, u2 in zip(tree1, tree2):
        if isinstance(u1, tuple) and isinstance(u2, tuple):
            compare_trees(u1, u2, indent)
        else:
            print(indent, 'item1', u1, 'item2', u2, 'equal', u1 == u2)

a = ((3, 2), 1, (4,), 5, (6, (7, 8)))
b = copy_tree(a)
print(b)
compare_trees(a, b)

output

((3, 2), 1, (4,), 5, (6, (7, 8)))
 tree1 ((3, 2), 1, (4,), 5, (6, (7, 8))) tree2 ((3, 2), 1, (4,), 5, (6, (7, 8))) identical False
   tree1 (3, 2) tree2 (3, 2) identical False
     item1 3 item2 3 equal True
     item1 2 item2 2 equal True
   item1 1 item2 1 equal True
   tree1 (4,) tree2 (4,) identical False
     item1 4 item2 4 equal True
   item1 5 item2 5 equal True
   tree1 (6, (7, 8)) tree2 (6, (7, 8)) identical False
     item1 6 item2 6 equal True
     tree1 (7, 8) tree2 (7, 8) identical False
       item1 7 item2 7 equal True
       item1 8 item2 8 equal True

I suppose that it's a little ironic that the test code is larger and more complex than the code we want to test, but sometimes that's inevitable. ;)

Answer 3

I think that the intention of the question was to use some sort of recursion. The following code would deep copy the tree recursively.

def copy_tree(tree):
    new_tree = ()
    for node in tree:
        if type(node) == tuple:
            new_tree += (copy_tree(node),)
        else:
            new_tree += (node,)
    return new_tree


a = ((3, 2), 1, (4,), 5)
b = copy_tree(a)

print(a[0] is b[0])

and the last print would give you False.

Answer 4

Here is a recursive solution that deep copies (nested) tuples, leaves other objects unchanged, and doesn't use the copy module:

def copy_tree(tree):
    if isinstance(tree, tuple):
        return tuple(map(copy_tree, tree))
        # or, maybe more readable
        # return tuple(copy_tree(x) for x in tree)
    return tree

Recursion is definitely the most elegant approach if you do not know nesting levels in advance.

Answer 5

Simply passing an existing tuple to the tuple constructor will not create a new copy of the constructor. Instead, you should pass an equivalent list to the tuple constructor to make a copy of a tuple:

def copy_tuple(t):
    output = []
    for i in t:
        if isinstance(i, tuple):
            output.append(copy_tuple(i))
        else:
            output.append(i)
    return tuple(output)

so that:

a = ((3, 2), 1, (4,), 5)
b = copy_tuple(a)
print(a)
print(b)
print(a[0] is b[0])

would output:

((3, 2), (4,), 5)
((3, 2), (4,), 5)
False

Answer 6

You should use the copy module.

This module has two functions to fit your needs, copy and deepcopy. copy does the same than copy_tree.

For example if you do :

import copy
l = [[0],[0]]
l2 = copy.copy(l)
l[0] = [1]
l[1][0] = [1]

Then l2 will be [[0],[1]] The first element of l2 has not changed because you replaced l first element. However, the second element has changed because you mutated the second element of l, which is a reference to the element of l2.

If you use deepcopy:

 import copy
 l = [[0],[0]]
 l2 = copy.deepcopy(l)
 l[0] = [1]
 l[1][0] = [1]

Then l2 will be [[0],[0]] because l and l2 does not share anything in common anymore.