Binary tree traversals example.

bin_tree_search.cpp

#include <iostream>
#include <functional>

/**
 * Easy way to distinguish between the 3 traversal methods is to check the position of the root.
 * If the root comes first -> pre-order
 * If the root comes last -> post-order
 * If the root comes in the middle -> in-order.
 */

template<typename T>
class Node {
  public:
    T val;
    Node* left;
    Node* right;

    Node(T val) {
      this->val = val;
      this->left = nullptr;
      this->right = nullptr;
    }

    // Root, Left, Right
    void pre_order_trav(std::function<void(T)> callback) {
      callback(val);

      if (left) {
        left->pre_order_trav(callback);
      }

      if (right) {
        right->pre_order_trav(callback);
      }
    }

    // Left, Right, Root
    void post_order_trav(std::function<void(T)> callback) {
      if (left) {
        left->post_order_trav(callback);
      }

      if (right) {
        right->post_order_trav(callback);
      }

      callback(val);
    }

    // Left, Root, Right
    void in_order_trav(std::function<void(T)> callback) {
      if (left) {
        left->post_order_trav(callback);
      }

      callback(val);

      if (right) {
        right->post_order_trav(callback);
      }
    }
};

int main() {
  //        6
  //     4    3
  //  8   2   1  7
  Node<int>* n = new Node<int>(6);
  n->left = new Node<int>(4);
  n->left->left = new Node<int>(8);
  n->left->right = new Node<int>(2);

  n->right = new Node<int>(3);
  n->right->left = new Node<int>(1);
  n->right->right = new Node<int>(7);

  std::cout << "Pre-order traversal:" << std::endl;
  n->pre_order_trav([](int val) {
      std::cout << val << " ";
  });
  std::cout << std::endl;

  std::cout << "Post-order traversal:" << std::endl;
  n->post_order_trav([](int val) {
      std::cout << val << " ";
  });
  std::cout << std::endl;

  std::cout << "In-order traversal:" << std::endl;
  n->in_order_trav([](int val) {
      std::cout << val << " ";
  });

  std::cout << std::endl;
}