Clone Binary Tree

Problem

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

Example

Given a binary tree:

    1
   / \
  2   3
 / \
4   5

return the new binary tree with same structure and same value:

    1
   / \
  2   3
 / \
4   5

Solution

Recursively clone the current node, then left sub-tree, then right sub-tree.