Question

C++ AVL tree

My AVL tree function

void inorder(AVLNode* t)
{
if (t == NULL)
return;
inorder(t->left);
cout << t->data.cancer_rate << " ";
inorder(t->right);
}

void inorder()
{
inorder(root);

}

Will Print my cancer city rate Inorder

example)...you can use any input as long it is a float

3.1

5.8

19.8

22.2

33.3

44.4

[Qustion]

How do I make a function that only prints the last one of my AVLTree ,in this case a function that only prints 44.4

And how do I make a function that only prints the first one of my AVLTree ,in this case a function that only prints 3.1

I think this can be accomplished by editing the inorder function

Answer 1

Let the newly inserted node be w

1) Perform standard BST insert for w

2) Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.

3) Re-balance the tree by performing appropriate rotations on the subtree rooted with z.

Here in this example, our first element is 3.1 and last element is 44.4

The C++ code to find the first(rightmost) and the last(leftmost) element is as following:

// C++ program to find leftmost and

// rightmost node from given preorder sequence

#include <bits/stdc++.h>

using namespace std;

// Function to return the leftmost and

// rightmost nodes of the BST whose

// preorder traversal is given

void LeftRightNode(int preorder[], int n)

{

    // Variables for finding minimum

    // and maximum values of the array

    int min = INT_MAX, max = INT_MIN;

    for (int i = 0; i < n; i++) {

         

        // Update the minimum

        if (min > preorder[i])

            min = preorder[i];

    

        // Update the maximum

        if (max < preorder[i])

            max = preorder[i];

    }

    // Print the values

    cout << "Leftmost node is " << min << "\n";

    cout << "Rightmost node is " << max;

}

// Code

int main()

{

    int preorder[] = { 3, 2, 1, 5, 4 };

    int n = 5;

    LeftRightNode(preorder, n);

    return 0;

}

Output:

Leftmost node is 3.1
Rightmost node is 44.4