Simple non balancing indexed binary search tree

Question

The following code represents a simple indexed binary search tree of integers. The insert method inserts an int. The indexed lookup looks up the ith smallest element (0 indexed). I'm trying to write C++ that is idiomatic, clean, modern, and efficient in that order. Can people give me pointers?

#include <iostream>
#include <pthread.h>
#include <type_traits>
#include <vector>
#include <algorithm>
#include <random>

using std::vector;

class IndexedBST{
  public:
    IndexedBST() : root(nullptr) {}
    void insert(int val){
      auto node = new Node(val, 1);
      if(root==nullptr){
        root = node;
      }
      else{
        auto pointer = root;
        Node * prev;
        while(pointer!=nullptr){
          ++pointer->size;
          prev = pointer;
          if(val < pointer->key){
            pointer = pointer->left;
          }
          else {
            pointer = pointer->right;
          }
        }
        if(prev->key>val)
          prev->left = node;
        else
         prev->right = node;
      }
    }
    int operator[](int i) const{
      if(root==nullptr||i<0||i>=root->size)
        throw std::out_of_range("Invalid index");
      auto pointer = root;
      while(1){
        auto left{pointer->left==nullptr?0:pointer->left->size}; 
        auto right{pointer->right==nullptr?0:pointer->right->size}; 
        if(i<left)
          pointer = pointer->left;
        else if (i==left)
          return pointer->key;
        else{
          i -= left+1;
          pointer = pointer->right;
        }
      }
    }
   
  private:  
    class Node
    {
      public:
        int key;
        int size;
        Node * left;
        Node * right;
        Node(int key, int size, Node * left = nullptr, Node * right = nullptr): key(key), size(size), left(left), right(right) {}
    };
    private:
      Node * root;
};

int main(int argc, char * argv[]) {
  vector<int> input(atoi(argv[1]), 0);
  vector<int> confirm(atoi(argv[1]), 0);


  for(int i=0; i<input.size(); i++){
    input[i] = confirm[i] = i;
  }
    auto rng = std::default_random_engine {};
  std::shuffle(std::begin(input), std::end(input), rng);

  IndexedBST bst;
  for(auto e:input)
    bst.insert(e);
  for(int i=0; i<input.size(); i++){
    if(bst[i]!=confirm[i]){
      printf("%d at %d does not match %d\n", bst[i], i, confirm[i]);
      break;
    }
  }
  printf("Checked %lu elements successfully\n", confirm.size());
}
```

Answer 1

Use unique_ptr for root, left, and right

Because each node of a binary tree owns memory for left and right children nodes, and a binary tree owns memory for the root node. This completely eliminates the need of delete, also reduces the headache of copy constructor/copy assignment operator problem (which arise because you used raw pointers as member variables)

Use better formatting and indentation

For better readability

Variable naming

I think node is better name than pointer

Prefer cout over printf

printf is bug-prone. If you're concerned on performance, use ios_base::sync_with_stdio(false)

Never leave local variable uninitialized

Always initialize raw pointers as nullptr, trivial typed objects as {0}, etc

Instead of comparing pointer with nullptr, use bool expression directly

C++ is already too verbose, you don't need to add another verbosity. You can use pointer->left ? pointer->left->size : 0 instead of pointer->left==nullptr?0:pointer->left->size

This is my rudimentary binary search tree for practicing purpose, you can refer this (https://github.com/frozenca/CLRS3/blob/main/12/12.3_insertion_and_deletion.cpp)

Answer 2

• More horizontal spacing please. Give your operators some breathing space. It is very hard to read things like root==nullptr||i<0||i>=root->size. BTW, I spent more time than necessary trying to parse prev->key>val. It looks almost like key itself is a pointer. prev->key > val is much more readable.

• Don't pass size to the Node()constructor. Your program relies on an important invariant, namely that node->size is always equal to node->left->size + node->right->size + 1. So (1) the size of a new node is easily inferred from left and `right, and (2) passing it explicitly may break the invariant.

• What is the purpose of right in operator[]?

• size should be size_t, not int.