4
\$\begingroup\$

I made a binary search tree implementation in C++ for my personal use in programming competitions.

#include <iostream>


using namespace std;

struct Node {
    int key;
    Node *leftnode;
    Node *rightnode;
    string value;
};

Node root_node; // Binary search tree

string inline query_bst(const int key) {
    Node *cur_node = &root_node;
    while (cur_node != NULL) {
        if (key == cur_node->key) {
            return cur_node->value;
        }
        if (key < cur_node->key) { /* value already returned, no need for else */
            cur_node = cur_node->leftnode;
        } else {
            cur_node = cur_node->rightnode;
        }
    }
    return ""; // Return empty string if not found
}    
void inline insert_bst(int key, string value) {
    Node *cur_node;
    Node *next_node = &root_node;
    // Search through bst for key
    while (next_node != NULL) {
        cur_node = next_node;
        if (key < cur_node->key) {
            next_node = cur_node->leftnode;
        } else {
            next_node = cur_node->rightnode;
        }
    }
    Node new_node;
    new_node.key = key;
    new_node.value = value;
    next_node = &new_node;
    if (key < cur_node->key) {
        cur_node->leftnode = next_node;
    } else {
        cur_node->rightnode = next_node;
    }
}

int main() {
    /* Test code */
    root_node.key = 1;
    insert_bst(2, "Node #3");
    insert_bst(3, "Node #4");
    cout << query_bst(3) << '\n'; 
}

I'm not generalizing the code or using OOP because I typically will only need one BST for programming competitions. insert_bst should be able to be redesigned so next_node is not required thereby reducing computation time and shortening the code. query_bst returns an awkward string when it fails to find an element. Overall, I believe the code is a bit bulky and requires optimization to be feasible for use in a programming competition.

\$\endgroup\$
  • \$\begingroup\$ Is it just me or is your code broken? The program crashes for me on insert_bst(3, "Node #4") and, if I comment that line out, on query_bst(3). \$\endgroup\$ – Kodnot Jun 7 '16 at 8:50
  • \$\begingroup\$ @Kodnot My code compiles and runs successfully for me. \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jun 7 '16 at 16:17
  • \$\begingroup\$ @CrazyPython It does? Hmm... It compiles successfully for me too, but it crashes when run. What do you work on? I'm using windows 7 x64, Code::Blocks 16.01 \$\endgroup\$ – Kodnot Jun 7 '16 at 17:06
  • \$\begingroup\$ @Kodnot Mac OS X Yosemite Clion BTW IMHO Clion (based on intellij) is a much better editor than Code::Blocks (I've used it before) \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jun 7 '16 at 17:07
  • \$\begingroup\$ Here's a slightly modified version that I just confirmed works perfectly: gist.github.com/CrazyPython/655c5702bf1ee58fdccdc68a67b7d35c \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jun 7 '16 at 17:09
2
\$\begingroup\$

First of all, your code does not work. In the "insert_bst" function, you create a Node named "new_node" and then assign the rightnode pointer that node's address. However, your "new_node" variable has automatic storage duration, and thus is destroyed at the end of the function. Therefore, after the function call is over, your pointer is pointing to unallocated memory (or something like that; my knowledge might be inadequate, I rarely deal with pointers). In order to avoid this, you need to use dynamic memory allocation.

Edit: To confirm my claims, I asked a question on StackOverflow.

Then, here is my version of inset_bst() function without next_node variable. However, I did not use it in the code, because I am not sure whether it actually improves the computation time, because it uses more if statemets. And I am too lazy to check :D

void insert_bst(int key, const std::string& value) {        
    Node *cur_node = &root_node;
    // Search through bst for key
    while (1) {
        if (key < cur_node->key) {
            if(cur_node->leftnode == nullptr) {
                cur_node->leftnode = new Node(key, value);
                break;
            }
            cur_node = cur_node->leftnode;
        } else {
            if(cur_node->rightnode == nullptr) {
                cur_node->rightnode = new Node(key, value);
                break;
            }
            cur_node = cur_node->rightnode;
        }
    }
}

Here is the modified code with the rest of my criticism/tips:

#include <iostream>

/**
    1. Avoid using "using namespace std". There are plenty of reasons why,
    google it if you doubt my word.
    2. Use nullptr instead of NULL macro
**/

struct Node {
    int key;
    Node *leftnode;
    Node *rightnode;
    std::string value;

    /** 3. It is always wise to use constructors instead of creating empty instances of
        structs / classes and then initializing member variables one by one
    **/
    Node(int tkey, const std::string& tvalue) : leftnode(nullptr), rightnode(nullptr), key(tkey), value(tvalue) {}

    //If you want the ability to construct nodes with undefined keys/values
    //Node() : leftnode(nullptr), rightnode(nullptr) {}
};

// I initialized it here for testing purposes, you did it in main, it doesn't really matter,
// except that previously the value of root_node was an empty string
Node root_node(1, "Node #1"); // Binary search tree

/**
    4. No need to use the "inline" specifier, at least in this case. The compiler usually
    can decide whether to inline functions by itself.
**/

std::string query_bst(const int key) {
    Node *cur_node = &root_node;
    while (cur_node != nullptr) {
        if (key == cur_node->key) {
            return cur_node->value;
        }
        if (key < cur_node->key) { /* value already returned, no need for else */
            cur_node = cur_node->leftnode;
        } else {
            cur_node = cur_node->rightnode;
        }
    }
    return ""; // Return empty string if not found
    /**
        5. If you don't want to return such awkward empty string, you might consider
        implementing some exception handling (i.e throw an std::runtime_error() with an
        appropriate error message on failure)
    **/
}

/**
    6. Pass strings by const ref if you are not going to modify them
**/
void insert_bst(int key, const std::string& value) {
    Node *cur_node;
    Node *next_node = &root_node;
    // Search through bst for key
    while (next_node != nullptr) {
        cur_node = next_node;
        if (key < cur_node->key) {
            next_node = cur_node->leftnode;
        } else {
            next_node = cur_node->rightnode;
        }
    }
    /**
        7. Currently your code allows duplicate keys. As I did not know whether such
        behaviour was intentional, I left it as it is.
    **/
    if (key < cur_node->key) {
        cur_node->leftnode = new Node(key, value);
    }
    else {
        cur_node->rightnode = new Node(key, value);
    }
}

/**
   8. Finally, with this modified code, you'd need to properly handle dynamically allocated
   memory. However, as your code did not provide any removal functions, I did not implement
   memory deallocation.
**/

int main() {
    /* Test code */
    //root_node.key = 1;
    insert_bst(2, "Node #2");
    insert_bst(3, "Node #3");
    std::cout << query_bst(3) << '\n';
}

Finally, here is the same code without all the comments:

#include <iostream>

struct Node {
    int key;
    Node *leftnode;
    Node *rightnode;
    std::string value;
    Node(int tkey, const std::string& tvalue) : leftnode(nullptr), rightnode(nullptr), key(tkey), value(tvalue) {}
};

Node root_node(1, "Node #1"); // Binary search tree

std::string query_bst(const int key) {
    Node *cur_node = &root_node;
    while (cur_node != nullptr) {
        if (key == cur_node->key) {
            return cur_node->value;
        }
        if (key < cur_node->key) { /* value already returned, no need for else */
            cur_node = cur_node->leftnode;
        } else {
            cur_node = cur_node->rightnode;
        }
    }
    return ""; // Return empty string if not found
}

void insert_bst(int key, const std::string& value) {
    Node *cur_node;
    Node *next_node = &root_node;
    // Search through bst for key
    while (next_node != nullptr) {
        cur_node = next_node;
        if (key < cur_node->key) {
            next_node = cur_node->leftnode;
        } else {
            next_node = cur_node->rightnode;
        }
    }
    if (key < cur_node->key) {
        cur_node->leftnode = new Node(key, value);
    }
    else {
        cur_node->rightnode = new Node(key, value);
    }
}

int main() {
    /* Test code */
    insert_bst(2, "Node #2");
    insert_bst(3, "Node #3");
    std::cout << query_bst(3) << '\n';
}
\$\endgroup\$
  • \$\begingroup\$ My test code works though. I don't like to use pointers but I have to in this case. Thanks for the other advice though. Have an up vote. \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Jun 7 '16 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.