0

I have this binary tree

    3
   / \
  9  20
    /  \
   15   7

i want to print its level order traversal in this format

[
  [3],
  [9,20],
  [15,7]
]

so i wrote this code using a queue and two lists 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new LinkedList<>();
        if(root!=null)
        {
            queue.add(root);
        }

        while(!queue.isEmpty())
        {
            int size=queue.size();
            for(int i=0;i<size;i++)
            {

            TreeNode tempNode=queue.poll();
            list.add(tempNode.val);
            if(tempNode.left!=null)
                queue.add(tempNode.left);
            if(tempNode.right!=null)
                queue.add(tempNode.right);
            }
            res.add(list);
            list.clear();

        }

        return res;

    }
}

but when i check the output it returns 

[[],[],[]]

i have spent more than 1 hour to debug the problem and i am convinced that my code is correct (which is not!) i dont know what is clearing the res list after i am adding the data to it. please help me to fix the error.

i believe list.clear() also clears the added list item in res.

of this is so then suppose 

x=34;
list.add(x);
x=45;
System.out.println(list); // it will still print [34]

but using list of list and after adding item to it and if you modify inner list.. it also modifies your list of list . why ?

int x=3;
li.add(x);
x=45;
res.add(li);
System.out.println(li);
li.remove(0);
li.add(23);
System.out.println(res);
Mridul Mittal
  • 19
  • 4
  • 1
    Start by replacing `list.clear();` with `list=new ArrayList<>();` – minus Jun 14 '19 at 12:19
  • Relevant: [Add an object to an ArrayList and modify it later](//stackoverflow.com/q/7080546) – 001 Jun 14 '19 at 12:21
  • Perhaps a duplicate of [Is Java “pass-by-reference” or “pass-by-value”?](https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) – Bernhard Barker Jun 14 '19 at 12:51

2 Answers2

1

This happens because you're manipulating an Object, it does not happen on primitive types

You're using a single list instance, after you add the list in the outer list, you're still manipulating the same one, you're alwys referencing the same List instance

You're adding it multiple times in the outer list and clear it, you need to create new instance at each iteration : 

while(!queue.isEmpty()){
    int size = queue.size();
    for(int i=0 ; i<size;i++){
        TreeNode tempNode = queue.poll();
        list.add(tempNode.val);
        if(tempNode.left!=null)
            queue.add(tempNode.left);
        if(tempNode.right!=null)
            queue.add(tempNode.right);
    }
    res.add(list);
    list = new ArrayList<>();
}
azro
  • 53,056
  • 7
  • 34
  • 70
0

my working code in c++ using level order traversal

output:

[
  [ 10 ],
  [ 11  9 ],
  [ 7  12  15  8 ],
  [ 13  14  16  18 ],
]

code:

#include <bits/stdc++.h> 
using namespace std; 


struct node{
    int key;
    struct node *left;
    struct node *right;
};


struct node *newnode(int key){
    struct node *Node= new node;
    Node->key=key;
    Node->left=NULL;
    Node->right=NULL;
    return Node;
}

void printNestedList(list<list<int> > nested_list) 
{ 
    cout << "[\n"; 

    list<list<int> >::iterator nested_list_itr; 

    for (nested_list_itr = nested_list.begin(); 
         nested_list_itr != nested_list.end(); 
         ++nested_list_itr) { 

        cout << "  ["; 

        list<int>::iterator single_list_itr; 

        list<int>& single_list_pointer = *nested_list_itr; 

        for (single_list_itr = single_list_pointer.begin(); 
             single_list_itr != single_list_pointer.end(); 
             single_list_itr++) { 
            cout << " " << *single_list_itr << " "; 
        } 
        cout << "],\n"; 
    } 
    cout << "]"; 
} 



void levelorder_traversal(struct node *temp){

    int l=1,level=1; 
    pair <struct node *, int> p;
    queue<pair <struct node *, int> > q;
    q.push(make_pair(temp, l));


    list<list<int> > nested_list; 
    list<int> single_list; 

    single_list.push_back(temp->key); 

    while(!q.empty()){

        struct node *temp= q.front().first;
        l= q.front().second;
        q.pop();

        if(temp->left){
            p = make_pair(temp->left, (l+1));
            q.push(p);

            if(l+1>level){
                nested_list.push_back(single_list);
                single_list.erase(single_list.begin(),single_list.end());
                level++;
            }
            single_list.push_back(temp->left->key);     
        }

        if(temp->right){
            p = make_pair(temp->right, (l+1));
            q.push(p);

            if(l+1>level){
                nested_list.push_back(single_list);
                single_list.erase(single_list.begin(),single_list.end());
                level++;
            }
            single_list.push_back(temp->right->key);            
        }

        if(q.empty()){
            nested_list.push_back(single_list);
        }   
    }
    cout<<endl;

    printNestedList(nested_list);     
}


int main(){

    struct node* root = newnode(10); 
    root->left = newnode(11); 
    root->left->left = newnode(7); 
    root->left->right = newnode(12); 
    root->right = newnode(9); 
    root->right->left = newnode(15); 
    root->right->right = newnode(8); 
    root->left->left->left = newnode(13); 
    root->left->left->right = newnode(14); 
    root->left->right->left = newnode(16); 
    root->left->right->right = newnode(18); 

    levelorder_traversal(root);
}
Deepak Kumrawat
  • 684
  • 1
  • 9
  • 14