CODEWITHSUNDEEP
c++algorithmbinary-search-tree
Nodar Dzamukashvili
Nodar Dzamukashvili

Reputation: 23

print BST min-max

I have a binary search tree (BST). I need to print it's values in such case: min, max, second min, second max...

For example: if the tree contains values 1,2,3,4,5,6,7, it should print: 1,7,2,6,3,5,4. I can't change the tree, or use another data structure like set or list. Also i need to do it in O(nlogn).

The nodes of BST are represented with struct:

struct nodeT{
    int value;
    nodeT * left;
    nodeT * right;
};

void PrintTree(nodeT * head){

}

Upvotes: 2

Views: 1352

Answers (4)

rafalio
rafalio

Reputation: 3946

Is the restriction on no other data structures purely pedagogical (fine if it is)? It would make things simpler if you could use another data structure. In case it isn't obvious, here is a way to do it in O(N) time (but O(N) space)

  • Traverse the N-element BST and get back the sorted array S in O(N) time, O(N) space.
  • print out S[0], S[N-1], S[1], S[N-2], S[2], ...

The other, recursive, way is outlined by the other answers.

Upvotes: 0

Fallen
Fallen

Reputation: 4565

  1. The minimum value is: if the root has no left child then the root. otherwise the leftmost node, such that the node that has no right branch from root to itself.

  2. The maximum value is: if the root has no right child then the root. otherwise the rightmost node that has no left branch from root to itself.

You can find these two using lg(N) operations in average case

So the complete algorithm becomes:

  1. Find the minimum value. Print it and delete the node. Note that printing and deleting takes lg(N) time
  2. If the tree is not empty, find the maximum value, print it and delete the node. Otherwise go to step 3.
  3. If the tree is not empty, return to step 1. otherwise terminate.

Runtime analysis : By definition, deleting a node in BST takes lg(N) time in average case and we've shown earlier that finding the max or min value takes lg(N) time too(in average case). So the runtime is O(NlgN) in average case.

Upvotes: 0

Kaidul
Kaidul

Reputation: 15915

In BST, The left subtree of a node contains only nodes with keys less than the node's key. And the right subtree of a node contains only nodes with keys greater than the node's key. So after a BST has been constructed, you should notice that - the minimum element should be in leftmost node and the maximum element should be in the rightmost node.

So You can do these by traversing the tree in the leftmost or rightmost position to retrieve the minimum/maximum element in O(log n) time:

struct treeNode {
    treeNode* left;
    treeNode* right;
    int key;
}*root;

template <class Object>
treeNode* BinarySearchTree <Object> :: minHelper(treeNode* &node) {
    if(node -> left == NULL) return node;
    else minHelper(node -> left);
}

template <class Object>
treeNode* BinarySearchTree <Object> :: min() {
    return minHelper(root);
}

template <class Object>
treeNode* BinarySearchTree <Object> :: maxHelper(treeNode* &node) {
    if(node -> right == NULL) return node;
    else maxHelper(node -> right);
}

template <class Object>
treeNode* BinarySearchTree <Object> :: max() {
    return maxHelper(root);
}

Here I wrote a complete program with all possible operations with BST

Upvotes: 0

Some programmer dude
Some programmer dude

Reputation: 409482

For the minimum you could have a function which recursively finds a value equal or larger than another value. You call this first with e.g. INT_MIN which means it will find the lowest value in the tree. Then you use the found value, add one, and call the same function again, and that will find the second smallest value, etc.

For the largest value, use the same basic algorithm, but check for equal or smaller than, and start with INT_MAX.

When the current "smallest" value found is larger than the current "largest" value, then you passed each other and end the searching.

Note 1: This works well with integer values, maybe not so well with floating point values.

Note 2: I have not put any regard to big-O, it's just something I thought of at the top of my head.

In pseudo code:

print_smallest_and_largest()
{
    int current_smallest = INT_MIN;
    int current_largest = INT_MAX;

    // Infinite loop
    for (;;)
    {
        current_smallest = find_equal_or_bigger_than(current_smallest);
        current_largest = find_equal_or_smaller_than(current_largest);

        if (current_smallest > current_largest)
            break;  // Got all values

        printf("Smallest: %d\n", current_smallest);
        printf("Largest: %d\n", current_largest);

        ++current_smallest;
        --current_largest;
    }
}

Upvotes: 1

Related Questions