Java: Breadth-First-Traversal Order Over an Array

Question

I wish to iterate over a sorted array in the order that a breadth first traversal would give if I put the array into a binary tree and performed a BFT on that (which is how I currently achieve this). Obviously this involves additional memory overhead since you need to build and store the array again in the binary tree. I know this should be similar to a binary search but I can't quite get the ordering right.

Here's how I currently achieve this:

BTree bst = sortedArrayToBST(array);
Queue<BTree> queue = new LinkedList<BTree>();
queue.add(bst);
while(!queue.isEmpty()) {
    BTree node = queue.remove();
    System.out.println(node.data);
    if(node.left != null) queue.add(node.left);
    if(node.right != null) queue.add(node.right);
}

Here's what I have currently (but this obviously gives the wrong ordering):

public void bstIterate(int[] array, int start, int end) {
    if(array.length == 0) return;
    int med = array.length /2;
    System.out.println(array[med]);
    bstIterate(array,start,mid);
    bstIterate(array,mid+1,array.length);
}

Can this be done without extra memory overhead, or do I have to store the items in a stack, vector or queue, and if so, how and would it require less memory than a binary tree?

Answer 1

I hope your sortedArrayToBST method is building a balanced binary tree from the given array. In that case the method you tried to implement will mimic a DFS (Depth first search) iteration over a BST. But your implementation is buggy, a correct implementation will look like this:

void bstIterate(int[] array, int start, int end) {
  if (start > end) return;
  int mid = start + (end - start) / 2; //it should not be array.lenght/2 because we are not updating the array at any point

  bstIterate(array, start, mid-1); // mid is already printed so we no longer need it
  bstIterate(array, mid+1, end);
}

//Now Call the method from you main
bstIterate(array, 0, array.length-1); //it should be array.length-1, as it is the last index of last element of the array

But from the question title I understand you are looking for BFS traversal over a sorted array by assuming the array as balanced binary tree.

Lets say our sorted array is this {1, 2, 3, 4, 5, 6, 7}. In that case a balanced BST will look like this:

    4
   / \
  2   6
 / \ / \
1  3 5  7

The BFS traversal on the above tree should output as follows: 4 2 6 1 3 5 7 I wrote a quick C++ implementation for this which will do the job in O(n) complexity (hope you can easily convert it to java):

#include <stdio.h>
#include <queue>
using namespace std;
class Node {
public:
    int start;
    int end;
};

void BFSiterate(int *arr, int start, int end) {
    queue<Node>que;
    Node n;
    n.start = start;
    n.end = end;
    que.push(n);

    while(!que.empty()) {
        n = que.front();
        que.pop();
        int mid = n.start + (n.end - n.start) / 2;
        printf("%d\n", arr[mid]);
        Node x;
        x.start = n.start;
        x.end = mid-1;
        if (x.start<=x.end)
            que.push(x); //left

        x.start = mid+1;
        x.end = n.end;
        if (x.start<=x.end)
            que.push(x); //right
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int len = sizeof(arr)/4;
    BFSiterate(arr, 0, len-1);
    return 0;
}

Answer 2

I'm not sure this is particularly efficient, but one possible solution is to pass a depth parameter to your bstIterate method and call it repeatedly with increasing depth until it returns no more results.

Something like this:

public static boolean bstIterate(int array[], int start, int end, int depth) {
  if (end <= start)
    return false;
  else {
    int mid = start + (end-start)/2;
    if (depth == 0) {
      System.out.println(array[mid]);
      return true;
    }
    else {
      boolean res1 = bstIterate(array, start, mid, depth-1);
      boolean res2 = bstIterate(array, mid+1, end, depth-1);
      return res1 || res2;
    }
  }
}

which you would call like this:

int depth = 0;
while (bstIterate(array, 0, array.length, depth))
  depth++;

Given this array:

int array[] = {1, 3, 4, 7, 9, 13, 18, 23, 25, 30};

that produces this tree:

                13
       4                 25
   3       9          23    30
1       7          18

and this output:

13
4
25
3
9
23
30
1
7
18

Is that what you had in mind?