CODEWITHSUNDEEP
arrayscsortingbinary-search-tree
Drake chmon
Drake chmon

Reputation: 87

Converting a BST to an array

I have a binary tree where I need to have it sorted inside an array and then return it. This is the function and where I am currently

struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;
};

typedef struct treeNode* BSTree;

static int* writeSortedToArray(const BSTree tree)
{
    int i=0;
    int leng = numberOfNodes(tree);
    int *arrayBST = malloc(leng*sizeof(int));

}

I dont know how to continue or if even the allocation part is correct any advice on how to make this work would be appreciated and if similar question has been asked before I would love it if anyone would guide me to it.

Upvotes: 3

Views: 1582

Answers (1)

Divyalok Jaiswal
Divyalok Jaiswal

Reputation: 104

First, you need to allocate your array properly.

This is how you can do it:

int* arrayBST = (int*)malloc(leng*sizeof(int));

Read more about it here: Dynamic Memory Allocation in C

Now, to store the tree in sorted order in the array, you need to traverse the left section of the tree, then root, and then the right section (you can do it recursively). This is called Inorder traversal (Tree Traversals). Just pass the above array in the inorder traversal function and store the root values while traversing.

The inorder traversal function can be like this:

typedef struct treeNode* BSTree; 

// you can pass the index in the array as reference
void inorderTraversal(const BSTree tree, int* arrayBST, int* ind) {
    if(tree) {
        //store the left subtree
        inorderTraversal(tree->left, arrayBST, ind);

        //store current root value
        arrayBST[*ind] = tree->data;
        (*ind)++;

        //store the right subtree
        inorderTraversal(tree->right, arrayBST, ind);
    }
}

static int* writeSortedToArray(const BSTree tree)
{
    int ind = 0;
    int leng = numberOfNodes(tree); 
    int* arrayBST = (int*)malloc(leng*sizeof(int));
    inorderTraversal(tree, arrayBST, &ind);
    return arrayBST;
}

I hope this helps. If you have any doubts, feel free to ask.

Upvotes: 3

Related Questions