How To Clone a binary tree with random pointers ?

Write an efficient code to clone a binary tree with each node containing an additional random pointer. The random pointer can point to any random node of the binary tree or can be null.

 
To clone a binary tree with random pointers, the intuitive solution is to maintain a hash table for each node in the binary tree. The idea is to traverse the binary tree in preorder fashion and for each encountered node, we create a new node with same data and create a mapping from the original node to the duplicate node in the hash table. After creating the mapping, we recursively set its left and right pointers. Finally, we traverse the original binary tree again and update random pointers of the duplicate nodes using the hash table.
This is demonstrated below in C++ and Java:
Output:

Preorder traversal of the original tree:
1 –> (2, 3, 2)
2 –> (4, 5, X)
4 –> (X, X, 3)
5 –> (X, X, 1)
3 –> (6, 7, X)
6 –> (X, X, 4)
7 –> (X, X, X)
Preorder traversal of the cloned tree:
1 –> (2, 3, 2)
2 –> (4, 5, X)
4 –> (X, X, 3)
5 –> (X, X, 1)
3 –> (6, 7, X)
6 –> (X, X, 4)
7 –> (X, X, X)

 
The time complexity of this solution is O(n), although with a linear space complexity. The extra space is used by the map and recursive call stack.