Clone Binary Tree

For the given binary tree, return a deep copy of it.

Question

For the given binary tree, return a deep copy of it.

Example:

Input: {1,2,3,4,5}
Output: {1,2,3,4,5}
Explanation:
The binary tree is look like this:
     1
   /  \
  2    3
 / \
4   5

Input: {1,2,3}
Output: {1,2,3}
Explanation:
The binary tree is look like this:
   1
 /  \
2    3

Analyzation

Recursion

Nothing to say. Just use the traditional way of doing binary tree problems.

The Code

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
        
        clone_root = TreeNode(root.val)
        clone_root.left = self.cloneTree(root.left)
        clone_root.right = self.cloneTree(root.right)
    
        return clone_root

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).