Clone a Tree

I've stumbled upon this problem multiple times, and solved it multiple times, but whenever I solve it, it always follows the same pattern in my mind: first I think it is easy-breezy. Then right before starting the code, I get confused with the exact recursion to be used. Takes me a minute or so to get my thoughts together and go back to the "easy-breezy" mindset.

It is not a hard problem indeed. Take care of the base case ("null? Bail"), create the target tree and add the first element. At that point in the recursion, always add the children first, and only then do the induction. It works. You can also accomplish the same by making the private function "return" a pointer to the tree. As a personal preference, I like to keep it a void function. But, it is just a preference. Cheers friends, take good care of yourselves! ACC.



public class Solution
{
    public Node CloneTree(Node root)
    {
        if (root == null) return null;

        Node retVal = new Node(root.val);
        CloneTree(root, retVal);

        return retVal;
    }

    private void CloneTree(Node source, Node target)
    {
        if (source == null || source.children == null) return;

        foreach (Node child in source.children)
        {
            target.children.Add(new Node(child.val));
            CloneTree(child, target.children[target.children.Count - 1]);
        }
    }
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons