patterncppMinor

Simple binary search tree for use in programming competitions

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

codereview cpp stackoverflow c++c++11 performance tree

simplesearchprogrammingbinaryforcompetitionsusetree

Problem

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

#include 

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 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 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 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.

Solution

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 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 

/**
    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 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 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 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

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 key) { / value already returned, no need for else /
cur_node = cur_node->leftnode;
} else {

Code Snippets

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;
        }
    }
}

#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';
}

#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';
}

Context

StackExchange Code Review Q#131264, answer score: 2

Revisions (0)

No revisions yet.