How to Iteratively Traverse a Binary Tree

Binary tree traversals are generally done in a recursive manner because this type of problem tends to be simplified by such methods. Nevertheless, the key advantage gained by using an iterative approach is the fact that the traversal will not run out of stack space. Moreover, there is always something to learn when solving a problem in an alternative way.

Below are the iterative implementations of the different types of traversals that can be done with a binary tree alongside an explanation of how they work:

Pre-Order Traversal

void print_pre_order(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }

    std::stack<TreeNode*> stack;
    stack.push(root);

    while (!empty(stack))
    {
        auto* node = stack.top();
        stack.pop();

        std::cout << node->val << ' ';

        if (node->right != nullptr)
        {
            stack.push(node->right);
        }
        if (node->left != nullptr)
        {
            stack.push(node->left);
        }
    }
}

Pre-Order traversal consists of traversing the left subtree before advancing to the right subtree. This behavior is achieved through the use of a Last In First Out (LIFO) data structure like a stack. The insertion of the right nodes occurs before the left nodes in order to make sure that the left nodes will be the first ones to be accessed.

Post-Order Traversal

void print_post_order(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }

    std::stack<TreeNode*> stack, out_stack;
    stack.push(root);

    while (!empty(stack))
    {
        auto* node = stack.top();
        stack.pop();

        out_stack.push(node);

        if (node->left != nullptr)
        {
            stack.push(node->left);
        }
        if (node->right != nullptr)
        {
            stack.push(node->right);
        }
    }

    while (!empty(out_stack))
    {
        auto* node = out_stack.top();
        out_stack.pop();

        std::cout << node->val << ' ';
    }
}

The Post-Order iterative tree traversal algorithm is slightly more complex than the Pre-Order one because the solution uses two stacks. The first stack gets the reverse Post-Order traversal in a similar manner to the algorithm used for the Pre-Order traversal with the only difference that the left node is inserted before the right one. The purpose of the second stack is to get the reverse of the first stack and in turn get the proper Post-Order traversal.

In-Order Traversal

void print_in_order(TreeNode* root)
{
    std::stack<TreeNode*> stack;
    auto* curr = root;

    while (!empty(stack) || curr != nullptr)
    {
        if (curr != nullptr)
        {
            stack.push(curr);
            curr = curr->left;
        }
        else
        {
            curr = stack.top();
            stack.pop();

            std::cout << curr->val << ' ';

            curr = curr->right;
        }
    }
}

In-Order traversal involves a current pointer pivot that will traverse the leftmost part of the tree and insert itself to a stack until it reaches a null value. If the current pointer is null and the stack is not empty then the pivot pointer moves towards the rightward node from the node at the top of the stack, otherwise, the traversal stops as the whole tree has been accessed.

Level-Order Traversal

void print_level_order(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }

    std::queue<TreeNode*> queue;
    queue.push(root);

    while (!empty(queue))
    {
        const auto LEVEL_SIZE = size(queue);

        for (std::size_t i = 0; i < LEVEL_SIZE; ++i)
        {
            auto* node = queue.front();
            queue.pop();

            std::cout << node->val << ' ';

            if (node->left != nullptr)
            {
                queue.push(node->left);
            }
            if (node->right != nullptr)
            {
                queue.push(node->right);
            }
        }
    }
}

The Level-Order traversal algorithm is different from all the previous methods mentioned in the fact that it uses a First In First Out (FIFO) data structure in the form of a queue. The way it works consists of accessing every node in a single level and then insert the left and right child nodes to use them in the next cycle of iteration for each upcoming level. As a side note, it is not necessary to include the for loop to iterate through every level of the tree as the queue itself will handle this behavior; nevertheless, this is added to make a distinction for every level of the tree that is being accessed.

Conclusion

Undoubtedly, the iterative approach of traversing a binary tree traversal is a more verbose and complex solution when compared to its recursive counterpart. Despite that, implementing another way of traversing a tree adds a level of comprehension for key data structures such as stacks and queues, as well as, include the benefit of not having to worry about running out of stack space.

Source Code

How to Format a String in C++

String formatting is a common and useful operation that is regularly used in most programming languages. Unfortunately, the formatting solution offered in the C++ Standard Library lacks simplicity and intuitiveness. For that reason, implementing a C-style “printf” type function for string formatting can be a worthy investment as it offers an advantage in terms of convenience over C++ I/O manipulators.

The implementation below makes use of several C++11 features that improve readability and safety concerns that would exist in older legacy code. The most notable one being the variadic template parameter pack that acts as a wrapper around the variadic function used in C-style “printf” methods.

template<typename... Args>
std::string format_string(const std::string& format, Args... args)
{
    const auto size = std::snprintf(nullptr, 0, format.c_str(), args...) + 1;
    const auto buffer = std::make_unique<char[]>(size);

    std::snprintf(buffer.get(), size, format.c_str(), args...);

    return std::string(buffer.get(), buffer.get() + size - 1);
}

Here’s a quick rundown of what is happening in this function:

  1. The size of the char array is determined by getting the return value from std::snprintf. (Note: plus one is added to this value to make room for the null terminator at the end of the array)

  2. A new char array is allocated through the use of a unique pointer to not worry about manually deleting this memory again.

  3. std::snprintf is used to write the formatted string into the char array.

  4. A new string is created from the char array buffer and then returned.

While this function seems to get the job done, there is still one more point missing to fully support C++ specific types. More specifically, this method doesn’t work whenever a std::string object is passed as part of its argument list. To fix this issue there needs to be an additional check to convert a std::string object into a “const char*” so that it gets forwarded as a parameter for std::snprintf. The complete implementation considering this aspect is shown below (Note: this solution uses C++17 features):

template<typename T>
auto convert(T&& t)
{
    if constexpr (std::is_same<std::remove_cv_t<std::remove_reference_t<T>>, std::string>::value)
    {
        return std::forward<T>(t).c_str();
    }
    else
    {
        return std::forward<T>(t);
    }
}

template<typename... Args>
std::string format_string_internal(const std::string& format, Args&& ... args)
{
    const auto size = std::snprintf(nullptr, 0, format.c_str(), std::forward<Args>(args)...) + 1;
    const auto buffer = std::make_unique<char[]>(size);

    std::snprintf(buffer.get(), size, format.c_str(), std::forward<Args>(args)...);

    return std::string(buffer.get(), buffer.get() + size - 1);
}

template<typename... Args>
std::string format_string(const std::string& format, Args&& ... args)
{
    return format_string_internal(format, convert(std::forward<Args>(args))...);
}

Now this solution may seem like a lot more complex than the previous one, but in reality, there is not a lot that has changed. The most noticeable difference is the inclusion of the “convert” function that checks at compile-time if the parameter passed is a string, and if it is then it returns the C-string given by the “c_str()” method, otherwise, it returns the type itself. Moreover, an additional format function is added to make sure the user does not have to explicitly call the “convert” method whenever formatting a string. Lastly, the use of std::forward is included to ensure perfect forwarding takes place.

Conclusion

C-style “printf” functions provide a simpler and more intuitive interface compared to the C++ standard solution of using I/O manipulators. Hence, the previous implementation for a string formatting function offers a great alternative from what can currently be done using C++ streams. As a side note, libraries like fmt and boost::format also provide great solutions to string formatting needs.

Source Code

How to Create a Random String in C++

Generating a random string in C++ is a simple task that can be easily achieved by the use of rand(); however, this method is not recommended because rand() lacks a distribution engine and the quality of its implementation leaves more to be desired. To combat this issue, the C++ Standard Library provides a set of functions from the Random header that allows users to generate random numbers from well-defined engines and distributions. The implementation of the function that generates a random string will make use of three key features present in the facilities of the Random header.

The elements used being:

The implementation for the random string generator combining all these features together is shown below:

std::string random_string(std::size_t length)
{
    const std::string characters = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

    std::random_device random_device;
    std::mt19937 generator(random_device());
    std::uniform_int_distribution<> distribution(0, characters.size() - 1);

    std::string random_string;

    for (std::size_t i = 0; i < length; ++i)
    {
        random_string += characters[distribution(generator)];
    }

    return random_string;
}

As you can see, this function hard codes all the possible characters that will be used to form the random string. Then, it initializes the three needed objects from the Random header by creating a Mersenne Twister engine and a distribution that covers all indexes from the possible characters string. Ultimately, it iterates through the arbitrary length given as a parameter to populate the string with a random character in every iteration.

Conclusion

Avoiding the use of rand() is a piece of advice that does not only apply to create random strings. Instead, it is recommended to use the facilities provided in the Random header that were included in the C++11 Standard Library.

Source Code

Concepts: The Next Major Change Coming to C++

The upcoming C++ standard is set to promise many different features and changes that will simplify and expand the way we write and think of code. Upon the wide variety of additions to the language, the inclusion of Concepts tops the list as the most significant one, as they are essential to simplify the use of generic programming. The currently ongoing CppCon has sparked my interest on the topic thanks to the talk given by Bjarne Stroustrup on the future of generic programming. Which covered the importance of concepts in the future of the language as described by the Concepts TS.

What is a Concept?

A Concept is a set of requirements that yield a boolean value at compile-time. They describe the characteristics needed for a certain group of objects to be used inside a template e.g.
Number: - Must provide arithmetic operators(+, +=, -, -=, *, *=, /, /=)
- Must be constructible from 0
- Must be copyable
- Must be movable

Why do we need Concepts?

- Simplify the way we write generic code by removing the verbosity and repetitiveness that templates bring e.g.

//Old C++ template version
template<typename T>
void sort(T& container)
{
    //Sort algorithm
}

//New C++ concept version
void sort(Sortable& container) //Sortable is a concept
{
    //Sort algorithm
}

- Provide more precise and helpful error messages which in the past have been known to daunting and irrelevant e.g.

int a = 42;

//Old error message 
sort(a) // -> error: 'a' doesn't have a [] operator

//New error message with concepts
sort(a) // -> error: 'a' is not Sortable (int doesn't provide [] operator)

- Allow the use of overloads for functions using concepts e. g.

template<RandomAccessIterator Iter>  //RandomAccessIterator is a concept
void distance(Iter first, Iter last)
{
  //Distance Implemnetation for random access iterators
}

template<Iterator Iter> //Iterator is a concept
void distance(Iter first, Iter last)
{
  //Distance implementation for the rest of iterators
}

- Remove the ugliness and complexity coming from the use of enable_if by replacing it with the use of the keyword requires e.g.

//Old code using enable_if
template<typename T>
class Foo
{
  public:
  template<typename U, std::enable_if<std::is_same<T, U>::value && std::is_copy_constructible<U>::value>>
  explicit Foo(const T& object) :
      object(object)
  {}

  private:
  T object;
};

//New code using concepts
template<typename T>
class Foo
{
  public:
  explicit Foo(const T& object)
  requires std::is_copy_constructible<T>::value :
  object(object)
  {}

  private:
  T object;
};


How do we use Concepts?

The first step is to either define a new concept or use an already existing one. Here is an example using the previously mentioned concept of a number:

template<typename T>
concept Number = requires(T a, T b)
{
  { a + b } -> T;
  { a += b } -> T&;
  { a - b } -> T;
  { a -= b } -> T&;
  { a * b } -> T;
  { a *= b } -> T&;
  { a / b } -> T;
  { a /= b } -> T&;
  
  { T{0} };
  
  requires std::is_copy_constructible<T>;
  requires std::is_move_constructible<T>;
}

Then we simply use the already defined concept in a function:

template<Number N>
N pow(N number)
{
  //power exponent implementation
}

Conclusion

Concepts fill in a void that was missing in the language; they effectively improve and simplify the use of generic code. It’s important to understand and appreciate their benefits to start adhering them into our code base as soon as C++20 arrives.