Need help : How are strings stored in memory during recursion?


  • 0
    A

    I have trouble understanding how strings are stored in the memory during recursion. In the following code we dont have to remove the last element added when we return from the function.(let [1,2,3] be the tree) i.e suppose "1-> 2" was added to the result and after returning from the function, the string remains "1->". So its behaving like a primitive variable during recursion, in the sense that the value is stored somewhere and retrieved when the function call returns. Since string is an object and is stored in the heap, I dont understand how this copy is maintained. Can anyone shed some light please?

    public class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> result = new ArrayList<>();
            generatePath(root, result, new String());
            return result;
        }
        
        public void generatePath(TreeNode root, List<String> result, String path) {
            
            if (root == null) {
                return;
            }
            
            if (root.left == null && root.right == null) {
                path += root.val;
                result.add(new String(path));
                return;
            }
            
            path += (root.val + "->");
            generatePath(root.left, result, path);
            generatePath(root.right, result, path);
            
            return;
            
        }
    }
    

    when using a mutable data structure the code was changed as below:

    public class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> result = new ArrayList<>();
            generatePath(root, result, new StringBuilder());
            return result;
        }
        
        public void generatePath(TreeNode root, List<String> result, StringBuilder path) {
            
            if (root == null) {
                return;
            }
            
            if (root.left == null && root.right == null) {
                int len = path.length();
                path.append(root.val);
                result.add(new String(path.toString()));
                path.delete(len,path.length());
                return;
            }
            int len = path.length();
            if(len == 0) len = 1;
            path.append(root.val+"->");
            generatePath(root.left, result, path);
            generatePath(root.right, result, path);
            path.delete(len,path.length());
            
            return;
            
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.