How to convert Node tree data to an ordered ArrayList array?

Question

public class Node {
private int data;

public int getData() {
    return data;
}

private Node left;
private Node right;

public Node(int d, Node l, Node r) {
    data = d;
    left = l;
    right = r;
}

// Deep copy constructor
public Node(Node o) {
    if (o == null) return;
    this.data = o.data;
    if (o.left != null) this.left = new Node(o.left);
    if (o.right != null) this.right = new Node(o.right);
}

public List<Integer> toList() {
// Recursive code here that returns an ordered list of the nodes
}

The full class is here: https://pastebin.com/nHwXMVrd

What recursive solution can I use to return an ordered ArrayList from integers inside Node? I tried a lot of things, but I had difficulty finding a recursive solution.

Answer 1

I'm not sure about Java, but that would be a general idea:

public List<Integer> toList() 
{
   List<Integer> newList = new List<Integer>();
   newList.add(this.data);
   if(left != null)
      newList.addAll(left.toList());
   if(right != null)
      newList.addAll(right.toList());
   return newList;
}

Answer 2

Given what you have bst, you can do a walk around inside, this will give you all the elements in ascending order (sorted), an example of how this is done:

 public List<Integer> toList() {
        return createOrderedList(this);
 }

 private List<Integer> createOrderedList(Node root) {
     if(root == null) {
         return new ArrayList<>();
     }

     List<Integer> list = new ArrayList<>();
     list.addAll(createOrderedList(root.left));
     list.add(root.data);
     list.addAll(createOrderedList(root.right));

     return list;
 }