CODEWITHSUNDEEP
javalistbinary-search-tree
Podo
Podo

Reputation: 709

Populate List with data from Binary Search Tree inOrder

I'm looking to store the values of a binary search tree in order in a List. I have a public method that calls the helper method, but when I print the list that's returned, i'm constantly getting an empty list...

public List inOrderList(){
    return inOrderList(overallRoot);   //root value
}

private List inOrderList(SearchTreeNode root){
    List<E> list1 = new ArrayList<E>();    //new list (will be returned)
    if(root==null){
        return list1;     //returns empty list
    }
     //List is NOT empty, let's do this thing.
    else {
        //create a new list, that calls left method recursive on left node
        List<E> podo = inOrderList(root.left);
        //Here, I *believe* we've reached the bottom. Add every podo to list1   
        list1.addAll(podo);

        //do the same thing for the right tree
        List<E> dopo = inOrderList(root.right);
        list1.addAll(dopo);        
   }

    //return the list we just filled from our BST
    return list1;
}

I elected not to try and fill my list with data alone. I figured using addAll and storing everything that way would be a better choice. Given that this solution was not working, I attempted storing data as well.

private List<Integer> inOrderList(IntTreeNode root){
    List<Integer> list1 = new ArrayList<Integer>();
    if(root==null){
        return list1;
    } else { 
        while(root!=null){
            List<Integer> podo = inOrderList(root.left);
            list1.add(root.data);
            List<Integer> dopo = inOrderList(root.right);
            list1.add(root.data);
        }
   
    }
    return list1;
}
  

I found that this at least filled the a list, however it simply inserted the root value twice and was done. I've been working on this for the last hour or so, and can't seem to come up with anything better, so I figured I'd turn to you guys.

Where am I going wrong/ how should I go about it?

Upvotes: 0

Views: 2550

Answers (2)

Podo
Podo

Reputation: 709

I realized I was pretty much just approaching it the wrong way.

Solution:

public List<E> inOrderList() {
List<E> list = new ArrayList<E>();
inOrderList(overallRoot, list);
return list;

}
//helper method
private void inOrderList(SearchTreeNode root, List<E> list) {
if(root == null)
    return;       
inOrderList(root.left, list);
list.add((E)root.data);
inOrderList(root.right, list);

}

Upvotes: 0

Anupam Saini
Anupam Saini

Reputation: 2421

In pseudo code your function would look something like this. I would recommend that you try the debugger and check how it works on a smaller input. 

private void inOrder(Node node, List<Integer> list) {
  if (node == null) {
    return;
  }
  inOrder(node.left, list);
  list.add(node.data);
  inOrderList(node.right, list);
}

Upvotes: 2

Related Questions