CODEWITHSUNDEEP
cbinary-search-tree
pydevd
pydevd

Reputation: 173

BST: print tree in sorted order using another key

I have next structures code in C for my binary tree:

struct student
{
    int studentID;
    char lastName[MAX_LENGTH];
    char firstName[MAX_LENGTH];
    float amount;
};

struct node
{
    struct student* record;
    struct node* left;
    struct node* right;
};

Records are inserted to the tree using studentID field as a key. When I'm printing the tree in order of studentID all is fine. But I want to print the SAME tree in order of lastName field.

I have only one idea: copy tree to array, sort array and display array.

Is there is any another solution?

Upvotes: 1

Views: 487

Answers (2)

Fred Foo
Fred Foo

Reputation: 363517

You can build and maintain multiple binary search trees in parallel, optionally folding them into a single multi-indexed data structure:

struct node {
    struct student *record;
    struct node *left_by_id, *right_by_id,
                *left_by_name, *right_by_name;
};

Obviously, all the BST operations have to be modified for this to work: e.g. to insert a new struct student*, you must tie a single node into two trees.

Upvotes: 1

exAres
exAres

Reputation: 4926

Create an index for lastName. You can use another BST which will store a lastName as key and a pointer to the corresponding node in your original BST.

struct indexNode {
    char lastName[MAX_LENGTH]
    struct node* originalNode;
};

You can go on inserting into this tree while inserting data in original tree.

This way you will have to spend O(log n) space to store extra index tree but will reduce your time for searching based on lastName to O(log n). Also, practically you will be storing only a key and pointer to a node for each element.

Upvotes: 0

Related Questions