/Binary Index Tree

              #include <iostream>
        using namespace std;
        
        template <typename T> class Node {
        public:
          Node<T>* left;
          Node<T>* right;
          T data;
        
          Node(T data) {
            this->data = data;
            this->left = nullptr;
            this->right = nullptr;
          }
        };
        
        template <typename T> class BinarySearchTree {
          Node<T>* root;
        public:
          BinarySearchTree() {
            root = nullptr;
          }
        
          void add(T value) {
            root = add(root, value);
          }
        
          Node<T>* add(Node<T>* r, T value) {
            if (r == nullptr) {
              return new Node<T>(value);
            }
            if (value > r->data) {
              r->right = add(r->right, value);
            }
            else {
              r->left = add(r->left, value);
            }
            return r;
          }
        
          void inOrder() {
            inOrder(root);
          }
        
          void inOrder(Node<T>* r) {
            if (r != nullptr) {
              inOrder(r->left);
              cout << r->data << " ";
              inOrder(r->right);
            }
          }
        
          void preOrder() {
            preOrder(root);
          }
        
          void preOrder(Node<T>* r) {
            if (r != nullptr) {
              cout << r->data << " ";
              preOrder(r->left);
              preOrder(r->right);
            }
          }
        
          void postOrder() {
            postOrder(root);
          }
        
          void postOrder(Node<T>* r) {
            if (r != nullptr) {
              postOrder(r->left);
              postOrder(r->right);
              cout << r->data << " ";
            }
          }
        
          // tim kiem
          bool search(T key) {
            return search(root, key);
          }
        
          bool search(Node<T>* r, T key) {
            if (!r) {
              return false;
            }
            if (r->data == key) {
              return true;
            }
        
            if (r->data < key) {
              return search(r->right, key);
            }
            else {
              return search(r->left, key);
            }
            return false;
          }
        
          int countNode() {
            return countNode(root);
          }
        
          int countNode(Node<T>* r) {
            if (r == nullptr) {
              return 0;
            }
            return 1 + countNode(r->left) + countNode(r->right);
          }
        
          int countLeafNode() {
            return countLeafNode(root);
          }
        
          int countLeafNode(Node<T>* r) {
            if (r == nullptr) {
              return 0;
            }
            if (r->left == nullptr && r->right == nullptr) {
              return 1;
            }
            return countLeafNode(r->left) + countLeafNode(r->right);
          }
        
        };
        
        int main() {
          BinarySearchTree<int> tree;
          tree.add(80);
          tree.add(50);
          tree.add(100);
          tree.add(30);
          tree.add(40);
          tree.add(20);
          tree.add(90);
          tree.add(120);
          tree.add(95);
          tree.add(130);
          tree.add(110);
          tree.inOrder(); cout << endl;
          cout << "So node tren cay: " << tree.countNode() << endl;
          cout << "So node la tren cay: " << tree.countLeafNode() << endl;
          // << "Ton tai node 30 tren cay? " << boolalpha << tree.search(30) << endl;
          //cout << "Ton tai node 10 tren cay? " << boolalpha << tree.search(10) << endl;
          // << "Ton tai node 110 tren cay? " << boolalpha << tree.search(110) << endl;
          return 0;
        }