How to push nodes from a Binary Tree into an Array?

Question

I am struggling with pushing values from a Binary Search Tree into an array, but I also need them to be sorted. Here are the instructions of what is needed.

The toArray method should create and return an array containing every element in the tree in sorted order ("in order"). The capacity of this array should equal the number of elements it contains. This method should make use of the recursive private helper method toArray(BSTNode, List) to generate the array. This array will need be created as an array of Comparable objects and cast to an array of E objects. You can use Collection's toArray(E[]) method to help with the array generation.

Therefore here is my code I have so far:

 public E[] toArray()
    {
        List<E> lista = new ArrayList<E>();
        toArray(root, lista);
        E[] good = (E[]) lista.toArray();
        return good;
    }
    private void toArray(BSTNode<E> node, List<E> aList)
    {
        if(node.left != null)
        {
            aList.add(node.left.data);
        }
    }

Here is the rest of the code for references, but I am more focused on the toArray methods more than anything. I can't figure out how to sort them into an array. Please help.

public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;

// post: constructs an empty search tree
public BinarySearchTree()
{
    root = null;
}

// post: value added to tree so as to preserve binary search tree
public void add(E value)
{
    root = add(root, value);
}
// post: value added to tree so as to preserve binary search tree
private BSTNode<E> add(BSTNode<E> node, E value)
{
    if (node == null)
    {
        node = new BSTNode<E>(value);
        numElements++;
    }
    else if (node.data.compareTo(value) > 0)
    {
        node.left = add(node.left, value);
    }
    else if (node.data.compareTo(value) < 0)
    {
        node.right = add(node.right, value);
    }
    return node;
}

// post: returns true if tree contains value, returns false otherwise
public boolean contains(E value)
{
    return contains(root, value);
}
// post: returns true if given tree contains value, returns false otherwise
private boolean contains(BSTNode<E> node, E value)
{
    if (node == null)
    {
        return false;
    }
    else
        {
        int compare = value.compareTo(node.data);
        if (compare == 0)
        {
            return true;
        }
        else if (compare < 0)
        {
            return contains(node.left, value);
        }
        else
            {   // compare > 0
            return contains(node.right, value);
        }
    }
}
    public void remove(E value)
    {
        root = remove(root, value);
    }
    private BSTNode<E> remove(BSTNode<E> node, E value)
    {
        if(node == null)
        {
            return null;
        }
        else if(node.data.compareTo(value) < 0)
        {
            node.right = remove(node.right, value);
        }
        else if(node.data.compareTo(value) > 0)
        {
            node.left = remove(node.left, value);
        }
        else
        {
            if(node.right == null)
            {
                numElements--;
                return node.left;// no R child; replace w/ L
            }
            else if(node.left == null)
            {
                numElements--;
                return node.right;   // no L child; replace w/ R
            }
            else
            {
                // both children; replace w/ max from L
                node.data = getMax(node.left);
                node.left = remove(node.left, node.data);
            }
        }
        return node;
    }
    private E getMax(BSTNode<E> node)
    {
        if(node.right == null)
        {
            return node.data;
        }
        else
        {
            return getMax(node.right);
        }
    }
    public void clear()
    {
        root = null;
        numElements--;
    }
    public boolean isEmpty()
    {
        if(numElements == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    public int size()
    {
        return numElements;
    }
    //My toArray Methods will go here. 
    public Iterator<E> iterator()
    {
        return new Iterator<>(root);
    }
    public static class Iterator<E>
    {
        private Stack<BSTNode<E>> stack;

        public Iterator(BSTNode<E> node)
        {
            this.stack = new Stack<>();
            while (node != null)
            {
                stack.push(node);
                node = node.left;
            }
        }
        public boolean hasNext()
        {
            return !stack.isEmpty();
        }
        public E next()
        {
            BSTNode<E> goodDays = stack.pop();
            E result = goodDays.data;
            if (goodDays.right != null)
            {
                goodDays = goodDays.right;
                while (goodDays != null)
                {
                    stack.push(goodDays);
                    goodDays = goodDays.left;
                }
            }
            return result;
        }
    }
private static class BSTNode<E>
{
    public E data;
    public BSTNode<E> left;
    public BSTNode<E> right;

    public BSTNode(E data)
    {
        this(data, null, null);
    }
    public BSTNode(E data, BSTNode<E> left, BSTNode<E> right)
    {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}
}

Your exercise has a focus on recursion, and asks for a recursive answer. Try first to fill in the method for a tree containing just 1 element. Then expand and call the "helper" method if either left or right exists — Ferrybig
– Ferrybig, Commented Apr 24, 2019 at 16:13
I would suggest you to start with pencil and paper and figure out how to do it first and then attempt to code it. — OscarRyz
– OscarRyz, Commented Apr 24, 2019 at 16:24
@Ferrybig Alright, I get that however I don't know how to write it in order for it to work. I can figure out the algorithm, I just don't know what exactly would go in there in order for it to be compared. — Adan Vivero
– Adan Vivero, Commented Apr 24, 2019 at 16:51
Write down the algorithm, test it on paper, with a couple of examples, then transform each step of your algorithm into a function. — OscarRyz
– OscarRyz, Commented Apr 24, 2019 at 17:02
I didn't realize you were already working with a sorted tree, I wrote down the steps to walk it. Should be pretty straight forward to implement, but just in case I posted the whole execution, I hope it adds clarity. — OscarRyz
– OscarRyz, Commented Apr 24, 2019 at 19:47

OscarRyz · Accepted Answer · 2019-04-24 19:41:40Z

Wait, this is a Binary Search Tree so it's already sorted.

Then you need to walk the tree.

Given you have something like:

To insert it you have to:

Given a tree root

A. If the tree is null, there's nothing to insert.
B. If is not null:
- B.1 Insert everything on the left
- B.2 Insert the tree root
- B.3 Insert everything on the right

Which would look like this:

void walkAndInsert(tree, array) {
    if (tree == null) {//A
        return
    } else { //B
      walkAndInsert(tree.left) //B.1
      array.add(tree.root) //B.2
      walkAndInsert(tree.right) //B.3
    }
}

So applying these steps on the array:

Is tree null? No, then execute step #B (insert all left, root and all right)

//B
tree = 
   4
 /   \
2      6
 \    /  \
  3  5    9

array =[]

We take the left branch and repeat the process (step #B.1, insert all the left):

Is tree null? No, then execute #B

//B.1
tree = 
2      
 \      
  3     

array =[]

Since the left branch is null, the next execution would like like this:

Is tree null ? yes, then return

//A
tree = 

array = []

This will conclude step B.1, we can go now to step B.2, insert root

//B.2
tree = 
2      
 \      
  3     

array =[2]

Followed by step B.3 insert all from right

Is tree null? No (there's a 3 there),

//B.3
tree =      
  3     

array =[2]

Then execute #B.1 on this tree

Is the tree empty? Yes, this concludes this B.1

//A
tree =      

array =[2]

Now in B.2 we insert this root

Is tree null? No (there's a 3 there),

//B.2
tree =      
  3     

array =[2,3]

And finally we go to B.3 insert all from right

But there's nothing there, so we just return

 //A
tree =      

array =[2,3]

This finishes the left branch from our very initial tree.

So after B.1 is finished on our initial tree, we execute B.2 and our data looks like:

// B.2 on the initial tree
tree = 
   4
 /   \
2      6
 \    /  \
  3  5    9

array =[2,3,4]

And we repeat with the right side

Is null? no, then B on the branch with 5, insert 6, and step B on the branch with 9

//B.3
tree = 
    6
   /  \
  5    9

array =[2,3,4]

// B.1
tree = 
    5

array =[2,3,4]

// A
tree = 


array =[2,3,4]

// B.2
tree = 
    5

array =[2,3,4,5]

// B.2
tree = 
    6
   /  \
  5    9

array =[2,3,4,5,6]

// B.3
tree = 
    9

array =[2,3,4,5,6]

// A
tree = 


array =[2,3,4,5,6]

// B.2
tree = 
    9

array =[2,3,4,5,6,9]

Adan Vivero · Accepted Answer · 2019-04-24 20:32:38Z

2

I figured it out. I will disclose the code and explain what's going on.

In the public I make a List that will soon be an Array List. Then I call the toArray helper method (private) to set the values. Root for the top one and lista for the list it will go in. After make the Array and set the size with numElements. Comparable is in there since at the very top of my code, that's what it extends. Then put the that array into the lista. Finally return it.

 public E[] toArray()
    {
        List<E> lista = new ArrayList<E>();
        toArray(root, lista);
        E[] arr = (E[]) new Comparable[numElements];
        lista.toArray(arr);
        return arr;
    }

In the private I do some recursion. As long as the node is not empty(null) then the array will search for left nodes continuously until it has no left (left) therefore add that into the array. Then adds the right ones.

 private void toArray(BSTNode<E> node, List<E> aList)
    {
        if(node != null)
        {
            toArray(node.left, aList);
            aList.add(node.data);
            toArray(node.right, aList);
        }
    }

Sorry if that was hard to understand, I'm not the best at explaining things, however this worked for me.

answered Apr 24, 2019 at 20:32

Adan Vivero

43213 silver badges41 bronze badges

2 Comments

OscarRyz Over a year ago

Perfect, this works because your BST has an iterator, right?

OscarRyz Over a year ago

Good! I included an example program out of my initial answer. This was entertaining to code :)

OscarRyz · Accepted Answer · 2019-04-24 20:48:49Z

Working example of the steps described here

import java.util.*;
import java.lang.reflect.Array;
import static java.lang.System.out;

class Tree<E extends Comparable<E>> {

    E root;
    Tree<E> left;
    Tree<E> right;

    void insert(E element) {
        if (this.root == null) {
            this.root = element;
            this.left = new Tree<E>();
            this.right = new Tree<E>();
        } else if (element.compareTo(this.root) < 0 ) {
            left.insert(element);
        } else {
            right.insert(element);
        }
    }

    E[] toArray() {
      List<E> a = new ArrayList<>();
      toArray(this, a);
      @SuppressWarnings("unchecked")
      final E[] r = a.toArray((E[]) Array.newInstance(a.get(0).getClass(), a.size()));
      return r;
    }

    // instance method just to retain the generic type E
    private void toArray(Tree<E> t, List<E> list) {
        if (t == null || t.root == null) {
            return;
        } else {
            toArray(t.left, list);
            list.add(t.root);
            toArray(t.right, list);
        }
    }

    public static void main(String ... args) {
        Tree<String> t = new Tree<>();
        t.insert("hola");
        t.insert("adios");
        t.insert("fuimonos");

        System.out.println(Arrays.toString(t.toArray()));
    }
}

Collectives™ on Stack Overflow

How to push nodes from a Binary Tree into an Array?

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related