CODEWITHSUNDEEP
arraysbinary-search-treeinorder
user2748161
user2748161

Reputation: 89

Storing BinarySearchTree inOrder traversal in an array

I have referred following link to see how inOrder traversal can be saved to an array Binary Search Tree to inOrder Array.

My tree:

       100
      /  \
    50    300
   / \
  20  70

When first element (20) is inserted into array index value is incremented to 1. Now when control goes to fetch next node (50) index value is becoming 0.

code: 

storeInOrder(root1,arr1,0);

private static void storeInOrder(Node root1, int[] arr1, int index) {       
    if(root1 == null){return;}

    storeInOrder(root1.left, arr1,index);       
    arr1[index++] = root1.data;
    storeInOrder(root1.right,arr1,index);
}

Expected output in array: 20 50 70 100 300
I am getting output as 100 300 0 0 0

Upvotes: 1

Views: 10867

Answers (2)

Codor
Codor

Reputation: 17605

The idea to put the logic in the visiting code is correct, but you need a global index. In your implemenation, the index you modify is passed by value, which does not result in the desired behaviour, as only local copies of the value are changed. A formulation in Java could look as follows.

int[] iArray; // initialize with the desired size
int GlobalIndex = 0;

void Visit(Node iNode)
{
    iArray[GlobalIndex++] = iNode.Data;
}

void StoreInOrder(Node iRoot)
{       
    if(null != iRoot)
    {
        StoreInOrder(iRoot.Left);       
        Visit(iRoot);
        StoreInOrder(iRoot.Right);
    }
}

Or alternatively, in a more contracted form closer to the original question.

int[] iArray; // initialize with the desired size
int GlobalIndex = 0;

void StoreInOrder(Node iRoot)
{       
    if(null != iRoot)
    {
        StoreInOrder(iRoot.Left);
        iArray[GlobalIndex++] = iNode.Data;
        StoreInOrder(iRoot.Right);
    }
}

If the implementation must be as close as possible to the original version, the following version could be used. It uses a wrapper class for int as a replacement for call by reference, as Java does not permit call by reference for elementary data types.

class IntWrapper
{
    public int Value;
    public IntWrapper(int InitialValue)
    {
        Value = InitialValue;
    }
}

int[] iArray;

StoreInOrder(iRoot, iArray, new IntWrapper() )

void StoreInOrder(Node iRoot, int[] iArray, IntWrapper Index)
{
    StoreInOrder(iRoot.Left,iArray,Index);
    iArray[Index.Value++] = iNode.Data;
    StoreInOrder(iRoot.Right,iArray,Index);
}

Upvotes: 1

Teddy Sterne
Teddy Sterne

Reputation: 14201

You can modify the function to return the last used index and then update based on the new index.

storeInOrder(root1,arr1);

private static void storeInOrder(Node root1, int[] arr1) {
    storeInOrderRecursive(root1,arr1,0);
}

private static Integer storeInOrderRecursive(Node root1, int[] arr1, int index) {       
    if(root1 == null){return index;}

    index = storeInOrderRecursive(root1.left, arr1,index);       
    arr1[index++] = root1.data;
    storeInOrderRecursive(root1.right,arr1,index);

    return index;
}

The wrapper function is not necessary but since you would always pass in 0 to storeInOrderRecursive this makes the API similar and then the return value can still be void for calls to storeInOrder.

Upvotes: 1

Related Questions