How to Copy a Binary Tree in Python

In this tutorial, we explain how to copy a binary tree in Python using a simple recursive method. A binary tree is a data structure in which every node has at most two children, called the left child and the right child.

We aim to create a duplicate of the provided binary tree, where each node in the original tree corresponds to a new node in the copy with the same value.

Step 1: Define a Node class

Let’s start by defining a Node class which represents a node in the binary tree. Each Node instance contains a value, in addition to pointers to its left and right children, if they exist.

1
2
3
4
5
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

Step 2: Define the recursive copy function

We now need to define a function to recursively copy each node in the binary tree. For each node, we create a new Node instance with the same value and recursively copy the left and right children.

1
2
3
4
5
def copy_tree(node):
    if node is None:
        return None
    else:
        return Node(node.value, copy_tree(node.left), copy_tree(node.right))

Step 3: Usage

Now you can create a binary tree and copy it using the functions we have defined.

1
2
3
4
5
6
7
8
9
# Create a binary tree
original_tree = Node(1)
original_tree.left = Node(2)
original_tree.right = Node(3)
original_tree.left.left = Node(4)
original_tree.left.right = Node(5)
 
# Copy the binary tree
copied_tree = copy_tree(original_tree)

Full Code

Here is the complete Python code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
 
def copy_tree(node):
    if node is None:
        return None
    else:
        return Node(node.value, copy_tree(node.left), copy_tree(node.right))
 
original_tree = Node(1)
original_tree.left = Node(2)
original_tree.right = Node(3)
original_tree.left.left = Node(4)
original_tree.left.right = Node(5)
 
copied_tree = copy_tree(original_tree)
 
print(original_tree)
print(copied_tree)
 
<__main__.Node object at 0x0000023A23CDED10>
<__main__.Node object at 0x0000023A23CDEF10>

Conclusion

It’s critical to understand that the duplicate binary tree and the original binary tree are two separate entities, even though their structures and node values are identical. Modifying one tree will not affect the other. This is useful in many contexts, when you may need to manipulate or transform a binary tree without changing the original data.