Generic in order traversal iterator for binary trees

Question

This actually started off as member type for the binary_search_tree, but after realizing that it doesn't compare to values or use the value objects inside of it, I decided to make it standalone. In fact, directly copy pasting it and playing with the template parameters made it work out of the box.

I got surprised by the simplicity of increment. I created the algorithm myself by making observations of the call stack of typical traversing through recursion.

---

Here is the algorithm for various operations of the iterator and requirements:

Node type

It should have left and right pointers to Node. The layout is not relevant, as iterator doesn't use any shady pointer arithmetic. ValueType can be manually specified, but defaut to the type of member value.

Construction

Start with a stack, prev_nodes, which contains nullptr. The reason for putting nullptr is that when tree is fully traversed, it needs some indication that traversing is over. nullptr seems to be the easiest solution to this problem. Initialize binary_tree_iterator to root of a tree. If left child exists, then on dereference it will give wrong node, thus use ++*this on it to get to the first right position if the left child exists.

Finding next node

If the left node of current is not nullptr and current != prev_nodes.top(), find leftmost node starting from the left of current. Assign current to the node found.

If the left node is nullptr or current == prev_nodes.top(), then it means that left side either doesn't exist or is already traversed. If current == prev_nodes.top(), pop it from the stack, as current is already visited. Try to go right (find leftmost child of current->right), and assign it to current. If right child doesn't exist, then it means that upward node is needed. Just current=prev_nodes.top(). Note that if the traversing is going upwards, every time prev_nodes.pop() will be executed and current = prev_nodes.top().

The rest should be obvious.

#ifndef ALGORITHMS_BINARY_TREE_ITERATOR_HPP
#define ALGORITHMS_BINARY_TREE_ITERATOR_HPP

#include <stack>
#include <iterator>
#include <type_traits>
#include <utility>
#include <cstddef>
#include <vector>

namespace shino
{

    template <typename Node, typename ValueType = decltype(std::declval<Node>().value)>
    class binary_tree_iterator
    {
        std::stack<Node*, std::vector<Node*>> prev_nodes;
        Node* current_node;
    public:
        using iterator_category = std::input_iterator_tag;
        using value_type = ValueType;
        using reference = const value_type&;
        using pointer = const value_type*;
        using distance = std::make_signed_t<std::size_t>;

        binary_tree_iterator() :
                current_node(nullptr)
        {
            prev_nodes.push(nullptr);
        }

        explicit binary_tree_iterator(Node* root)
        {
            prev_nodes.push(nullptr);
            current_node = root;
            if (current_node != nullptr and current_node->left != nullptr)
                ++*this;
        }

        const ValueType& operator*()
        {
            return current_node->value;
        }

        binary_tree_iterator& operator++()
        {
            if (current_node->left != nullptr and prev_nodes.top() != current_node)
            {
                prev_nodes.push(current_node);
                current_node = next(current_node->left);
            }
            else
            {
                if (current_node == prev_nodes.top())
                    prev_nodes.pop();
                if (current_node->right != nullptr)
                    current_node = next(current_node->right);
                else
                    current_node = prev_nodes.top();
            }

            return *this;
        }

        bool operator!=(const binary_tree_iterator& rhs)
        {
            return rhs.current_node != current_node;
        }

    private:
        Node* next(Node* start_pos)
        {
            if (start_pos->left != nullptr)
            {
                prev_nodes.push(start_pos);
                return next(start_pos->left);
            }
            else
                return start_pos;
        }
    };
}

#endif //ALGORITHMS_BINARY_TREE_ITERATOR_HPP

Concern

• Suboptimal (?) stack usage

  I don't think that spare nullptr matters, but maybe I could use it in a better way?

• Different increment algorithm?

  Currently the asymptotic seems to be the height of the left subtree on the arrival, but otherwise constant time (I have no idea how to calculate asymptotic, except simple cases). The performance seems to be terrible though, bubble sort easily outperformed binary search tree sorting. I guess binary search tree should be used for searching.

Example

I dumped the iterator, binary search tree and automatic tests here for your convenience (please note that nothing is changed about binary search tree, but if you have any suggestions, they are welcome):

#ifndef ALGORITHMS_BINARY_TREE_ITERATOR_HPP
#define ALGORITHMS_BINARY_TREE_ITERATOR_HPP

#include <stack>
#include <iterator>
#include <type_traits>
#include <utility>
#include <cstddef>
#include <vector>

namespace shino
{

    template <typename Node, typename ValueType = decltype(std::declval<Node>().value)>
    class binary_tree_iterator
    {
        std::stack<Node*, std::vector<Node*>> prev_nodes;
        Node* current_node;
    public:
        using iterator_category = std::input_iterator_tag;
        using value_type = ValueType;
        using reference = const value_type&;
        using pointer = const value_type*;
        using distance = std::make_signed_t<std::size_t>;

        binary_tree_iterator() :
                current_node(nullptr)
        {
            prev_nodes.push(nullptr);
        }

        explicit binary_tree_iterator(Node* root)
        {
            prev_nodes.push(nullptr);
            current_node = root;
            if (current_node != nullptr and current_node->left != nullptr)
                ++*this;
        }

        const ValueType& operator*()
        {
            return current_node->value;
        }

        binary_tree_iterator& operator++()
        {
            if (current_node->left != nullptr and prev_nodes.top() != current_node)
            {
                prev_nodes.push(current_node);
                current_node = next(current_node->left);
            }
            else
            {
                if (current_node == prev_nodes.top())
                    prev_nodes.pop();
                if (current_node->right != nullptr)
                    current_node = next(current_node->right);
                else
                    current_node = prev_nodes.top();
            }

            return *this;
        }

        bool operator!=(const binary_tree_iterator& rhs)
        {
            return rhs.current_node != current_node;
        }

    private:
        Node* next(Node* start_pos)
        {
            if (start_pos->left != nullptr)
            {
                prev_nodes.push(start_pos);
                return next(start_pos->left);
            }
            else
                return start_pos;
        }
    };
}

#endif //ALGORITHMS_BINARY_TREE_ITERATOR_HPP
#ifndef ALGORITHMS_BINARY_SEARCH_TREE_HPP
#define ALGORITHMS_BINARY_SEARCH_TREE_HPP

#include "binary_tree_iterator.hpp"
#include <ostream>
#include <utility>

namespace shino
{
    template <typename ValueType>
    class binary_search_tree
    {
        struct node
        {
            const ValueType value;
            node* left;
            node* right;
        };

        enum class direction
        {
            is_root,
            left,
            right
        };

        struct search_result
        {
            //actually used in structured binding,
            // but clion doesn't recognize that
            node* parent;
            node* target_child;
            direction parent_to_child;
        };

        node* root;
    public:
        using iterator = binary_tree_iterator<node>;

        binary_search_tree() :
                root(nullptr)
        {}

        binary_search_tree(const binary_search_tree& other) = delete;

        binary_search_tree& operator=(const binary_search_tree& other) = delete;

        binary_search_tree(binary_search_tree&& other) noexcept:
                root(std::exchange(other.root, nullptr))
        {}

        binary_search_tree& operator=(binary_search_tree&& other) noexcept
        {
            std::swap(root, other.root);
            return *this;
        }

        bool try_insert(const ValueType& value)
        {
            return try_insert_helper(value, root);
        }

        bool exists(const ValueType& value)
        {
            return find_node(value, nullptr, root, direction::is_root).target_child != nullptr;
        }

        bool delete_if_exists(const ValueType& value)
        {
            auto[parent_node, node_with_value, parent_to_child] =
            find_node(value, nullptr, root, direction::is_root);

            if (node_with_value == nullptr)
                return false;

            if (node_with_value->left == nullptr)
            {
                auto old = node_with_value;
                switch (parent_to_child)
                {
                    case direction::left:
                        parent_node->left = node_with_value->left;
                        break;
                    case direction::right:
                        parent_node->right = node_with_value->right;
                        break;
                    case direction::is_root:
                        root = root->right;
                }
                delete old;
                return true;
            }

            if (node_with_value->left->right == nullptr)
            {
                switch (parent_to_child)
                {
                    case direction::left:
                        parent_node->left = node_with_value->right;
                        node_with_value->right->left = node_with_value->left;
                        break;
                    case direction::right:
                        parent_node->right = node_with_value->right;
                        node_with_value->right->left = node_with_value->left;
                        break;
                    case direction::is_root:
                        root->left->right = root->right;
                        root = root->left;
                }
                delete node_with_value;
                return true;
            }

            auto[suitable_parent, suitable_node] =
            find_suitable_node(node_with_value->left->right, node_with_value->left);
            switch (parent_to_child)
            {
                case direction::left:
                    parent_node->left = suitable_node;
                    suitable_node->right = node_with_value->right;
                    suitable_node->left = node_with_value->left;
                    break;
                case direction::right:
                    parent_node->right = suitable_node;
                    suitable_node->right = node_with_value->right;
                    suitable_node->left = node_with_value->left;

                    break;
                case direction::is_root:
                    suitable_node->right = root->right;
                    suitable_node->left = root->left;
                    root = suitable_node;
            }
            suitable_parent->right = nullptr;
            delete node_with_value;

            return true;
        }

        void clear()
        {
            clear_helper(root);
        }

        void inorder_print(std::ostream& os)
        {
            for (const auto& x: *this)
            {
                os << x << ' ';
            }
        }

        iterator begin()
        {
            return iterator{root};
        }

        iterator end()
        {
            return {};
        }

        ~binary_search_tree()
        {
            clear();
        }

    private:
        std::pair<node*, node*> find_suitable_node(node* start_position, node* parent)
        {
            if (start_position->right == nullptr)
                return {parent, start_position};
            return find_suitable_node(start_position->right, start_position);
        }

        void clear_helper(node* start_position)
        {
            if (start_position == nullptr)
                return;
            clear_helper(start_position->left);
            clear_helper(start_position->right);

            delete start_position;
        }

        search_result find_node(const ValueType& value,
                                node* parent,
                                node* current_node,
                                direction parent_to_child)
        {
            if (current_node == nullptr)
                return {nullptr, nullptr, direction::is_root};

            if (current_node->value == value)
                return {parent, current_node, parent_to_child};

            if (value < current_node->value)
                return find_node(value, current_node, current_node->left, direction::left);
            else
                return find_node(value, current_node, current_node->right, direction::right);
        }

        bool exists_helper(const ValueType& value,
                           node* current_node)
        {
            if (current_node == nullptr)
                return false;
            if (current_node->value == value)
                return true;

            if (value < current_node->value)
                return exists_helper(value, current_node->left);
            else
                return exists_helper(value, current_node->right);
        }

        void inorder_print_helper(std::ostream& os,
                                  node*& current_node)
        {
            if (current_node == nullptr)
                return;

            inorder_print_helper(os, current_node->left);
            os << current_node->value << ' ';
            inorder_print_helper(os, current_node->right);
        }

        bool try_insert_helper(const ValueType& value,
                               node*& current_node)
        {
            if (current_node == nullptr)
            {
                current_node = new node{value};
                return true;
            }

            if (current_node->value == value)
                return false;

            if (current_node->value > value)
                return try_insert_helper(value, current_node->left);
            else
                return try_insert_helper(value, current_node->right);
        }
    };
}

#endif //ALGORITHMS_BINARY_SEARCH_TREE_HPP

#include <random>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <vector>

std::vector<int> generate_unique_numbers(std::size_t size)
{
    std::vector<int> result;
    if (size == 0)
        return {};

    static std::mt19937_64 twister;
    std::uniform_int_distribution<> distribution{0, static_cast<int>(size - 1)};

    std::unordered_set<int> numbers;
    while (numbers.size() != size)
    {
        numbers.insert(distribution(twister));
    }

    return {numbers.begin(), numbers.end()};
}

void run_randomized_tests()
{
    for (std::size_t i = 0; i <= 10'000; ++i)
    {
        std::cout << "running binary_search_tree test on size " << i << '\n';
        auto numbers = generate_unique_numbers(i);
        shino::binary_search_tree<int> tree;
        for (auto x: numbers)
            tree.try_insert(x);

        std::sort(numbers.begin(), numbers.end());
        std::size_t numbers_index = 0;
        for (auto x: tree)
        {
            if (x != numbers[numbers_index++])
                throw std::logic_error{"tree binary_tree_iterator is broken on size " + std::to_string(i)};
        }
    }
}

int main(){
    std::cout << "running remove case 1...\n";
    test_remove_case_one();
    std::cout << "remove case 1 passed successfully\n";
    std::cout << "running remove case 2...\n";
    test_remove_case_two();
    std::cout << "remove case 2 passed successfully\n";
    std::cout << "running remove case 3...\n";
    test_remove_case_three();
    std::cout << "remove case 3 passed successfully\n";
//
    std::cout << "running randomized tests...\n";
    run_randomized_tests();
    std::cout << "randomized tests passed successfully\n";
    shino::binary_search_tree<int> tree;
}

Answer 1

• It looks like input_iterator_tag is too restrictive. As implemented, it complies with the forward iterator requirements.

• The gut feeling is that it must be an inner class of a tree. After all, not everything providing left and right pointer has a semantics of a tree node. Consider a double-linked list for example.

• The recursiveness of next makes it harder (at least for me) to follow the flow. Consider an iterative rewrite:

      Node * next (Node * start_pos) {
          while (start_pos->left != nullptr) {
              prev_nodes.push(start_pos);
              start_pos = start_pos.left;
          }
          return start_pos;
      }   
  

• operator++ hardwires in-order traversal. It makes sense for BST, but looks too restrictive for a general case.

• The condition current_node->left != nullptr and prev_nodes.top() != current_node is hard to read. Consider negating it:

          if (current_node->left == nullptr or current_node == prev_nodes.top()) {
              if (current_node == prev_nodes.top())
                  prev_nodes.pop();
              if (current_node->right != nullptr)
                  current_node = next(current_node->right);
              else
                  current_node = prev_nodes.top();
          } else {
              prev_nodes.push(current_node);
              current_node = next(current_node->left);
          }
  

• I am not sure why you omit operator==.

Answer 2

Your constructors can be simplified: use default initializers in-line in the class!

    std::stack<Node*, std::vector<Node*>> prev_nodes = {nullptr};
    Node* current_node = nullptr;
     ⋮
    binary_tree_iterator() =default;  // you don’t even have to mention it!

    explicit binary_tree_iterator(Node* root)
    : current_node { root }
    {
        if (current_node && current_node->left)
            ++*this;
    }

Note that the remaining initialiation in the second constructor is put into the member init list where it should be, and the body of that function shows two other things:

Don’t compare against nullptr (as explained in the previous review of your binary tree), and your use of the digraph and alternative for && is strange and might be hard for people to read.

---

You seem to have done a sound job in putting together the proper iterator traits, but they are not in the std::iterator_traits template!