0

I have encountered several places while solving problems using recursion and lists that the results change drastically, when a deep copy of list is passed vs shallow copy. For example, in the code snippet below (to print all root to leaf paths in a binary tree), passing the shallow copy of the list in the left and right subtree recursive calls, gives incorrect results. While passing a deep copy works as expected.

Can anyone explain what's the difference between the two and specifically, how it makes a difference in recursion.

Thanks in advance !

List<List<Integer>> result = new ArrayList();
public void getPath(TreeNode root, List<Integer> path) {
if(root == null)
   return;
path.add(root.val);
if(root.left == null && root.right == null) {
   this.result.add(path);
   return;
}
else {
   getPath(root.left, new ArrayList(path));
   getPath(root.right, new ArrayList(path));

   //getPath(root.left, path);
   //getPath(root.right, path);
}

}
jcoder12
  • 167
  • 1
  • 4
  • 15
  • 1
    Forget about recursion for a sec as that isn't directly relevant. Do you understand what the difference is between a shallow and a deep copy? – Carcigenicate Sep 12 '19 at 15:29
  • Yes. I have already read a very informative post on this - https://stackoverflow.com/questions/184710/what-is-the-difference-between-a-deep-copy-and-a-shallow-copy. But I am not able to put the pieces together in this reference. Any explanation is appreciated. – jcoder12 Sep 12 '19 at 15:36
  • 1
    `path` is modified within `getPath` and with a shallow copy this will basically affect _all_ invocations, not just the current one. – Marvin Sep 12 '19 at 15:43

0 Answers0