1. Recursion

Here's a visualization of the tree we're given:

To solve this problem, we want to use recursion. This means we want to write cloneTree(root) using cloneTree(other nodes).

To clone the tree, we need to first clone the root node of the tree. After we do that, we need to point the cloned root node to the clones of the children nodes. Below is a picture of this. The dashed node indicates the cloned node is not the same node as before - it's a new node, different from the original.

Here's the recursive equation for this:

2. Base case

The recursion calls itself on lower and lower nodes in the tree. It eventually calls itself on a null node cloneTree(None), which gives an error. We need to manually find what cloneTree(None) is equal to, since the recursion doesn't work here. The clone of a null node is just equal to a null node.

3. Code

To code this up, we just make a function that always returns what cloneTree is equal to. That way the function is guaranteed to be correct. The function is equal to the recursion, unless we're in the base case, in which case it's equal to None. Here's the full code:

Time Complexity $O(n)$. We visit every node once and do O(1) operations per node, giving O(n)*O(1) = O(n).

Space Complexity $O(n)$. For now, you don't need to know where this comes from - we'll go over the full details in the next lesson "Call Stack". Just know the computer needs some memory to keep track of the function calls it's making.