Problem

For each node in a binary search tree, create a duplicate of the node, and insert the duplicate as the left child of the original node. The updated tree should preserve its binary search property.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

 Input:  
     2
    / \
   1   3
 
 Output:
        2
       / \
      2   3
     /   /
    1   3
   /
  1
Explanation:  
Each node is duplicated as the left child:  
- Node `2` gets a duplicate left child `2`.  
- Node `1` gets a duplicate left child `1`.  
- Node `3` gets a duplicate left child `3`.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

Input:  
  10
 /  \
5   20

Output:
	  10
     /  \
    10   20
   /    /
  5    20
 /
5

Explanation:  
Each node is duplicated as the left child:  
- Node `10` gets a duplicate left child `10`.  
- Node `5` gets a duplicate left child `5`.  
- Node `20` gets a duplicate left child `20`.

Solution

Method 1 - Using preorder traversal

The problem is exactly as described — for each node, a duplicate needs to be created and inserted as the left child. Importantly, the binary search tree property is maintained since the duplicate nodes appear as left children without disrupting the order of left (smaller values) and right (greater values) descendants.

Approach

  1. Traverse the tree using a depth-first search (DFS).
  2. At each node:
    • Create a duplicate node with the same value.
    • Insert this duplicate as the left child of the current node.
    • Point the duplicate’s left child to the original left subtree.
  3. Continue recursively on the original left and right children of the tree.
  4. Return the modified tree.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class Solution {

    // Definition for a binary tree node
    static class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    // Function to create duplicate nodes
    public void duplicateTree(TreeNode root) {
        if (root == null) {
            return;
        }

        // Create duplicate node
        TreeNode duplicate = new TreeNode(root.val);

        // Attach duplicate as the left child
        duplicate.left = root.left;
        root.left = duplicate;

        // Recursive calls for original left and right children
        duplicateTree(duplicate.left);
        duplicateTree(root.right);
    }

    // Helper function to print tree (inorder traversal)
    public void print(TreeNode root) {
        if (root == null) return;
        print(root.left);
        System.out.print(root.val + " ");
        print(root.right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        System.out.println("Original Tree:");
        sol.print(root);

        // Transform
        sol.duplicateTree(root);

        System.out.println("\nTransformed Tree:");
        sol.print(root);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution:
    def duplicateTree(self, root):
        if root is None:
            return

        # Create duplicate node
        duplicate = TreeNode(root.val)

        # Attach duplicate as the left child
        duplicate.left = root.left
        root.left = duplicate

        # Recursive calls for original left and right children
        self.duplicateTree(duplicate.left)
        self.duplicateTree(root.right)

    def printTree(self, root):
        # Helper function to print the tree (inorder traversal)
        if root is None:
            return
        self.printTree(root.left)
        print(root.val, end=" ")
        self.printTree(root.right)


# Driver code
if __name__ == "__main__":
    solution = Solution()

    # Example tree
    root = TreeNode(2)
    root.left = TreeNode(1)
    root.right = TreeNode(3)

    print("Original Tree:")
    solution.printTree(root)

    # Transform the tree
    solution.duplicateTree(root)

    print("\nTransformed Tree:")
    solution.printTree(root)

Complexity

  • ⏰ Time complexity: O(n) — Each node is visited once, and inserting duplicates is O(1).
  • 🧺 Space complexity: O(h) — Recursion depth depends on the height of the tree (h).