Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Why is my preorder traversal returning an empty list?

I am trying to understand why code is returning an empty list.
I am not looking for a solution to the problem.
The solution already exists in What is wrong with my Preorder traversal?

I want to understand, what is incorrect about my current understanding of recursion and the call stack upon using a global variable.

class Solution {
    ArrayList<Integer> list;
    public List<Integer> preorderTraversal(TreeNode root) {
        list = new ArrayList<Integer>();
        preOrder(root);
        return list;
    }
    public void preOrder(TreeNode node){
        System.out.println(list.toString());
        if(node == null)
            return;
        
        list.add(node.val);
        
        //System.out.println(list.toString());
        
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }
}

For the following tree : [1,null,2,3]

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

I notice that in the first print call
I get 7 empty lists

[]
[]
[]
[]
[]
[]
[]

In my second print call, I get the following

[1]
[2]
[3]

Why isn’t my global variable list not "saving" or "appending" to the next call stack?
It seems like, there are multiple list objects being utilized.

>Solution :

Because you use preorderTraversal with left and right nodes so each time it will override list value with a new empty list, you should use preOrder with left and right node like this

public void preOrder(TreeNode node){
    if(node == null)
        return;
        
    list.add(node.val);
        
    preOrder(node.left);
    preOrder(node.right);
}
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading