AVLTree program keeps timing out.

Hi, I am trying to balance an AVL tree with 10 nodes. When I run the code in Xcode, it works fine and passes all three tests, but I am getting a timeout error when I try and submit this project. There is an AVLTree class with helper functions in use as well. I am truly lost.

//AVLTree.h

#include <iostream>

class AVLTree {
public:
int data;
uint32_t height;
AVLTree* parent;
AVLTree* left;
AVLTree* right;

//base functions defined for you
AVLTree(int data, AVLTree* parent=nullptr, AVLTree* left=nullptr, AVLTree* right=nullptr);
bool isLeaf();
uint32_t getHeight();

//*******************
//functions you need to define

//insert a node and rebalance tree to maintain AVL balanced tree
//return new root of tree
AVLTree* insert(int data);

//computes a node's balance factor by subtracting the right subtree height from the left subtree height.
int getBalance();

//checks for imbalance and rebalances if neccessary
//return new root of tree
AVLTree* rebalance();


//implement a right rotate
//return new root of tree
AVLTree* rotateRight();

//implement a left rotate
//return new root of tree
AVLTree* rotateLeft();

//Do not edit these three functions
bool isBalanced();
uint32_t countNodes();
void updateHeight();
};

//AVLTree.cpp

#include "AVLTree.h"

#include <iostream>

using namespace std;
//************** already implemented helper functions
AVLTree::AVLTree(int t_data, AVLTree* t_parent, AVLTree* t_left, AVLTree* t_right) {
data = t_data;
height = 0;
parent = t_parent;
left = t_left;
right = t_right;
}

bool AVLTree::isLeaf() {
return ((left == nullptr) and (right == nullptr));
}

uint32_t AVLTree::getHeight() {
if (left == nullptr && right == nullptr) {
return 0;
}
int i = max (left == nullptr ? 0 : left -> getHeight(), right == nullptr ? 0 : right -> getHeight()) + 1;
return i;
}

//******************************************************

int AVLTree::getBalance() {
int i = (left == nullptr ? 0 : left->height) - (right == nullptr ? 0 : right->height);
int j = abs(i);
return j;
}

AVLTree* AVLTree::rotateRight() {
AVLTree* u = left;
left = u->right;
u->right = this;
return u;
}

AVLTree* AVLTree::rotateLeft() {
AVLTree* u = right;
right = u->left;
u->left = this;
return u;

}

AVLTree* AVLTree::rebalance() {
if (isLeaf()) {
return this;
}
if (left != nullptr) {
left = left -> rebalance();
}
if (right != nullptr) {
right = right -> rebalance();
}

int isBal = isBalanced();
if (!isBal) {
// Rebalance this (me)

if ((left == nullptr ? 0 : left -> getHeight()) < (right == nullptr ? 0 : right -> getHeight())) {
if (right -> left != nullptr) {
right = right -> rotateRight();
AVLTree *t = rotateLeft();

return t;
}
else if(right -> right != nullptr) {
AVLTree *t = rotateLeft();

return t;
}
}
else if ((left == nullptr ? 0 : left -> getHeight()) > (right == nullptr ? 0 : right -> getHeight())) {
if (left -> right != nullptr) {
left = left -> rotateLeft();
AVLTree *t = rotateRight();

return t;
}
else if(left -> left != nullptr) {
AVLTree *t = rotateRight();

return t;
}
}
}
return this;
}

AVLTree* AVLTree::insert(int new_data) {
AVLTree *root = this;
if (new_data < data) {
if (this -> left != nullptr)
{
left = left -> insert(new_data);
}
else {
this -> left = new AVLTree(new_data, this);
}
}
else if (new_data > data) {
if (this -> right != nullptr)
{
right = right -> insert(new_data);
}
else {
this -> right = new AVLTree(new_data, this);
}
}

// always return the root!
root -> updateHeight();

bool isBal = isBalanced();
if (isBal == false) {
AVLTree *rtn = rebalance();

rtn -> updateHeight();
return rtn;
}

return root;
}




//***************************
//Do not edit code below here
uint32_t AVLTree::countNodes() {
if (isLeaf()) {
return 1;
}
if (left != nullptr) {
if (right != nullptr) {
return 1 + left->countNodes() + right->countNodes();
}
return 1+ left->countNodes();
}
return 1 + right->countNodes();
}

void AVLTree::updateHeight() {
if (isLeaf()) {
height = 0;
return;
}
if (left != nullptr) {
left->updateHeight();
if (right != nullptr) {
right->updateHeight();
height = (1 + max(left->getHeight(), right->getHeight()));
return;
}
height = 1 + left->getHeight();
return;
}
right->updateHeight();
height = 1 + right->getHeight();
return;
}

bool AVLTree::isBalanced() {
if ( isLeaf() ) {
return true;
}
if (left == nullptr) {
return ( right->getHeight() < 1 );
}
if (right == nullptr) {
return ( left->getHeight() < 1 );
}
return ( left->isBalanced() and right->isBalanced() and abs(getBalance() < 2) );
}

//Main.cpp

#include <fstream>
#include <iostream>
#include <cmath>
#include <time.h>
#include <stack>
#include <queue>

#include "AVLTree.h"

using namespace std;


int main() {

AVLTree* tree1Root = new AVLTree(50, nullptr);
srand(time(NULL));
uint32_t numNodes = 10;
for (uint32_t i=1; i < numNodes; i++ ) {
tree1Root = tree1Root->insert(( rand() % 10000));


std::cout<<"Balanced? "<< tree1Root -> isBalanced() <<std::endl;
}

// //Uncomment to help debug lost nodes
//// if (tree1Root->countNodes() != i+2) {
//// std::cout<<"Lost node "<<std::endl;
//// return 1;
//// }
//
// //uncomment to help debug unbalanced trees
//// tree1Root->updateHeight();
//// if ( ! tree1Root->isBalanced() ) {
//// std::cout<<"Tree1Root balanced: FAILED at node insertion "<<i<<std::endl;
//// return 1;
//// }
//
// }

if (tree1Root->countNodes() == numNodes) {
std::cout<<"tree1Root lost Nodes: PASSED"<<std::endl;
}
else {
std::cout<<"tree1Root lost Nodes: FAILED expected: 10 actual: "<<tree1Root->countNodes()<<std::endl;
}

tree1Root->updateHeight();
float expectedHeight = log2(numNodes) * 1.5;
if (tree1Root->getHeight() < expectedHeight) {
std::cout<<"tree1Root height: PASSED"<<std::endl;
}
else {
std::cout<<"tree1Root height: FAILED expected: <" <<expectedHeight<<" actual: "<<tree1Root->getHeight()<<std::endl;
}

if ( tree1Root->isBalanced()) {
std::cout<<"Tree1Root is balanced: PASSED"<<std::endl;
}
else {
std::cout<<"Tree1Root is balanced: FAILED"<<std::endl;
}
}



How are you submitting it? Are you trying to use gsubmit? What does the error look like? More info would be helpful in order for us to help you.
Please edit your post to include code tags.
https://www.cplusplus.com/articles/jEywvCM9/
Registered users can post here. Sign in or register to post.