CODEWITHSUNDEEP
javasortingbinary-search-tree
MosesA
MosesA

Reputation: 965

Turning a Binary Tree to a sorted array

Is there a way to turn a Binary to a sorted array without having to traverse the tree for every array index?

Node root;
Node runner;
int current_smallest;

void findsmallest(Node root){
    //Pre-order traversal
    if(root == null){
        return;
    }else{
        runner = root;
        if(current_smallest == null){
            current_smallest = runner.element;
        }else{
            if(current_smallest > runner.element){
            current_smallest = runner.element;
            }
        }
        findsmallest(runner.left);
        findsmallest(runner.right);
    }   
}

void fill_array( int [] array ){

    for(int i =0; i < array.length(); i++){
        findsmallest(root);
        array[i] = current_smallest;
    }
}

As you can see this can be take a long time if there are a lot of nodes in the tree. Btw, I forgot to show that the whole tree would have to be traversed at the start to get the length of the array.

Upvotes: 7

Views: 30802

Answers (4)

Deepak K Sahu
Deepak K Sahu

Reputation: 1

Here is java code for same:

int[] result = new int[9];
fillArray(tree, result, 0);

public int fillArray(Tree tree, int[] result, int index) {
        if (tree.left != null) {
            index = fillArray(tree.left, result, index);
        }
        result[index++] = tree.val;

        if (tree.right != null) {
            index = fillArray(tree.right, result, index);
        }

   return index;
}

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727137

Yes, you can do that: run an in-order traversal of the tree, keep the current position of the array, and store the node's value at the then-current position of the array.

You can do in-order traversal recursively, or you can do it with a stack data structure. If you want to do it recursively, you can do this:

int fill_array(Node root, int [] array, int pos) {
    if (root.left != null) {
        pos = fill_array(root.left, array, pos);
    }
    array[pos++] = root.element;
    if (root.right != null) {
        pos = fill_array(root.right, array, pos);
    }
    return pos; // return the last position filled in by this invocation
}

Note that in order for the above recursive procedure to work, the caller must allocate enough space in the array passed into the function.

Upvotes: 18

femtoRgon
femtoRgon

Reputation: 33351

What you want is an in-order traversal, which is generally implemented recursively like:

  • Traverse left subtree.
  • Handle this node (ie. insert as the next element in your array)
  • Traverse right subtree.

Upvotes: 5

Tom
Tom

Reputation: 2399

A binary tree can be represented in an array; if this were the case, all you would need to do is sort the array.

Here's some more info on representing the tree in the array: wikipedia

This is not necessarily the most space-efficient representation; the "nodes with references" representation may waste less space.

Upvotes: 5

Related Questions