bst_smart.cpp

#include <iostream>
#include <array>
#include <functional>
#include <memory>

template<typename T>
using Ptr = std::unique_ptr<T>;

template<typename T>
struct Node {
  T val;
  Ptr<Node<T>> left;
  Ptr<Node<T>> right;

  Node(T myval) : val(myval), left(nullptr), right(nullptr) {}
};

template<typename T>
using NodePtr = Ptr<Node<T>>;

template <typename T>
void insert(NodePtr<T>& root, T val){

  if(root == nullptr){
    root = std::make_unique<Node<T>>(val);
    return;
  }

  NodePtr<T>* pnode = &root;
  while(*pnode != nullptr){
    pnode = (val <= (*pnode)->val) ? &(*pnode)->left : &(*pnode)->right;
  }
  *pnode = std::make_unique<Node<T>>(val);
}

template <typename T>
void traverse(NodePtr<T>& root){
  // Using a unique_ptr to manage the counter
  auto counter = std::make_unique<int>(0);

  std::function<void(NodePtr<T>&, std::unique_ptr<int>&)> traverse_imp =
    [&](NodePtr<T>& node, std::unique_ptr<int>& counter) {
      if (node == nullptr) {
        return;
      }

      traverse_imp(node->left, counter);

      if (*counter > 0) {
        std::cout << " -> ";
      }
      std::cout << node->val << "(" << *counter << ") ";
      (*counter)++;

      traverse_imp(node->right, counter);
  };

  traverse_imp(root, counter);
}

template<typename T, int size>
NodePtr<T> create_bst_from_array(const std::array<T, size>& x){
  NodePtr<T> root = nullptr;
  for(const T& val: x){
     insert(root, val);
  }
  return root;
}

using IntNodePtr = NodePtr<int>;

int main(){
  constexpr int N = 10;
  std::array<int, N> data = {4,1,67,24,3,12,35,30,98,23};
  IntNodePtr root = create_bst_from_array<int, N>(data);
  traverse(root);

}