in-order BST traversal

inOrder_space(1)_time(N).cpp

#define CATCH_CONFIG_MAIN
#include "catch.hpp"
using namespace std;

enum Dir {
  topDir,
  leftDir,
  rightDir
};

class Node {
  public:
  Node(int key) : itsKey(key), itsParent(nullptr) {
  }

  const int itsKey;
  unique_ptr<Node> itsLeft;
  unique_ptr<Node> itsRight;
  const Node *itsParent;
};

vector<int> InOrder(const Node *root) {
  Dir fromDir = topDir;
  vector<int> keys;

  while (root != nullptr) {

    if (fromDir == topDir) {

      if (root->itsLeft) root = root->itsLeft.get();
      else fromDir = leftDir;

    }

    if (fromDir == leftDir) {

      keys.push_back(root->itsKey);

      if (root->itsRight) {

        root = root->itsRight.get();
        fromDir = topDir;

      } else fromDir = rightDir;

    }

    if (fromDir == rightDir) {

        if (root->itsParent != nullptr) fromDir = (root->itsKey <= root->itsParent->itsKey) ? leftDir : rightDir;

        root = root->itsParent;

    }

  }

  return keys;

}

TEST_CASE("") {

  SECTION("trivial") {

    REQUIRE(InOrder(nullptr) == vector<int>());
    REQUIRE(InOrder(make_unique<Node>(5).get()) == vector<int>({5}));

  }

  SECTION("root(left)") {
    const unique_ptr<Node> root = make_unique<Node>(5);

    root->itsLeft = make_unique<Node>(3);
    root->itsLeft->itsParent = root.get();
    REQUIRE(InOrder(root.get()) == vector<int>({3, 5}));

  }

  SECTION("root(right)") {
    const unique_ptr<Node> root = make_unique<Node>(5);

    root->itsRight = make_unique<Node>(7);
    root->itsRight->itsParent = root.get();
    REQUIRE(InOrder(root.get()) == vector<int>({5, 7}));

  }

  SECTION("root(left, right)") {
    const unique_ptr<Node> root = make_unique<Node>(5);

    root->itsLeft = make_unique<Node>(3);
    root->itsLeft->itsParent = root.get();
    root->itsRight = make_unique<Node>(7);
    root->itsRight->itsParent = root.get();
    REQUIRE(InOrder(root.get()) == vector<int>({3, 5, 7}));

  }

}

inOrder_space(D)_time(N).cpp

#define CATCH_CONFIG_MAIN
#include "catch.hpp"
#include <stack>
using namespace std;

class Node {
  public:
  Node(int key, unique_ptr<Node> &&left, unique_ptr<Node> &&right) : itsKey(key), itsLeft(move(left)), itsRight(move(right)) {
  }

  const int itsKey;
  const unique_ptr<Node> itsLeft;
  const unique_ptr<Node> itsRight;
};

vector<int> InOrder(Node *root) {
  vector<int> keys;
  stack<Node *> parents;

  while (root != nullptr || !parents.empty()) {

    if (root == nullptr) {

      root = parents.top();
      parents.pop();
      keys.push_back(root->itsKey);
      root = root->itsRight.get();

    } else {

      parents.push(root);
      root = root->itsLeft.get();

    }

  }

  return keys;

}

TEST_CASE("") {

  REQUIRE(InOrder(nullptr) == vector<int>());
  REQUIRE(InOrder(make_unique<Node>(5, nullptr, nullptr).get()) == vector<int>({5}));
  REQUIRE(InOrder(make_unique<Node>(5, make_unique<Node>(3, nullptr, nullptr), nullptr).get()) == vector<int>({3, 5}));
  REQUIRE(InOrder(make_unique<Node>(5, nullptr, make_unique<Node>(7, nullptr, nullptr)).get()) == vector<int>({5, 7}));
  REQUIRE(InOrder(make_unique<Node>(5, make_unique<Node>(3, nullptr, nullptr), make_unique<Node>(7, nullptr, nullptr)).get()) == vector<int>({3, 5, 7}));

}