Pre-oder and post-order tree traversal using iterators (C++ VS Python)

tree-traversal.cpp

#include <iterator>
#include <stack>
#include <utility>
#include <vector>

class Node {
  using Children = std::vector<Node>;
  int n;
  Children children;
  class PreOrderRange {
    class Iterator {
      std::stack<Node *> next;

    public:
      explicit Iterator(Node *root) {
        if (root)
          next.push(root);
      }
      Node &operator*() { return *next.top(); }
      const Node &operator*() const { return *next.top(); }
      Iterator operator++() {
        // remove currentNode
        auto currentNode = next.top();
        next.pop();
        // add all children to stack
        auto &children = currentNode->getChildren();
        for (auto it = children.rbegin(); it != children.rend(); it++)
          next.push(&(*it));
        return *this;
      }
      bool operator!=(Iterator &rhs) const { return next != rhs.next; }
      bool operator==(Iterator &rhs) const { return next == rhs.next; }
    };
    Node *root;

  public:
    explicit PreOrderRange(Node *root) : root(root) {}
    Iterator begin() { return Iterator(root); }
    Iterator end() { return Iterator(nullptr); }
  };
  class PostOrderRange {
    class Iterator {
      struct NodeInfo {
        Node *node;
        bool isExpanded;
        bool operator==(const NodeInfo &rhs) const {
          return node == rhs.node && isExpanded == rhs.isExpanded;
        }
      };
      std::stack<NodeInfo> next;
      void expandTop() {
        while (!next.top().isExpanded) {
          next.top().isExpanded = true;
          auto &children = next.top().node->getChildren();
          for (auto it = children.rbegin(); it != children.rend(); it++)
            next.push({&(*it), false});
        }
      }

    public:
      explicit Iterator(Node *root) {
        if (root) {
          next.push({root, false});
          expandTop();
        }
      }
      Node &operator*() { return *next.top().node; }
      const Node &operator*() const { return *next.top().node; }
      Iterator operator++() {
        next.pop();
        if (!next.empty())
          expandTop();
        return *this;
      }
      bool operator!=(Iterator &rhs) const { return next != rhs.next; }
      bool operator==(Iterator &rhs) const { return next == rhs.next; }
    };
    Node *root;

  public:
    explicit PostOrderRange(Node *root) : root(root) {}
    Iterator begin() { return Iterator(root); }
    Iterator end() { return Iterator(nullptr); }
  };

public:
  Node(int n, Children children = {}) : n(n), children(std::move(children)) {}
  int getN() const { return n; }

  Children &getChildren() { return children; }
  const Children &getChildren() const { return children; }

  PreOrderRange preOrderTraversal() { return PreOrderRange(this); }
  PostOrderRange postOrderTraversal() { return PostOrderRange(this); }
};

void visit(const Node &n);

void traversePreOrder_Recursive(const Node &n) {
  visit(n);
  for (auto &ch : n.getChildren())
    traversePreOrder_Recursive(ch);
}

void traversePreOrder_Iterative(const Node &n) {
  std::stack<const Node *> next;
  next.push(&n);
  while (!next.empty()) {
    auto currentNode = next.top();
    next.pop();
    visit(*currentNode);
    auto &children = currentNode->getChildren();
    for (auto it = children.rbegin(); it != children.rend(); it++)
      next.push(&(*it));
  }
}

void traversePostOrder_Recursive(const Node &n) {
  for (auto &ch : n.getChildren())
    traversePostOrder_Recursive(ch);
  visit(n);
}

void traversePostOrder_Iterative(const Node &n) {
  std::stack<std::pair<const Node *, bool>> next;
  next.push({&n, false});
  while (!next.empty()) {
    while (!next.top().second) {
      next.top().second = true;
      auto &children = next.top().first->getChildren();
      for (auto it = children.rbegin(); it != children.rend(); it++)
        next.push({&(*it), false});
    }
    auto currentNode = next.top().first;
    next.pop();
    visit(*currentNode);
  }
}

#include <iostream>

void visit(const Node &n) { std::cout << n.getN() << " "; }

int main() {
  //      |          (0)           |
  //      |        /  |  \         |
  //      |       /   |   \        |
  //      |      /    |    \       |
  //      |   (1)    (2)    (3)    |
  //      |  / | \  / | \  / | \   |
  //      |  4 5 6  7 8 9 10 11 12 |
  Node tree{0, {{1, {4, 5, 6}}, {2, {7, 8, 9}}, {3, {10, 11, 12}}}};
  std::cout << "preorder traversal (recursive):\t\t";
  traversePreOrder_Recursive(tree);
  std::cout << "\n";
  std::cout << "preorder traversal (iterative):\t\t";
  traversePreOrder_Iterative(tree);
  std::cout << "\n";
  std::cout << "preorder traversal (using iterator):\t";
  for (const auto &n : tree.preOrderTraversal())
    std::cout << n.getN() << " ";
  std::cout << "\n\n";

  std::cout << "postorder traversal (recursive):\t";
  traversePostOrder_Recursive(tree);
  std::cout << "\n";
  std::cout << "postorder traversal (iterative):\t";
  traversePostOrder_Iterative(tree);
  std::cout << "\n";
  std::cout << "postorder traversal (using iterator):\t";
  for (const auto &n : tree.postOrderTraversal())
    std::cout << n.getN() << " ";
  std::cout << "\n";
  return 0;
}

tree-traversal.py

class Node:
    def __init__(self, n, children=None):
        self.n = n
        self.children = children if children else []

    def pre_order_iter(self):
        yield self.n
        for ch in self.children:
            for node in ch.pre_order_iter():
                yield node

    def post_order_iter(self):
        for ch in self.children:
            for node in ch.post_order_iter():
                yield node
        yield self.n


if __name__ == "__main__":
    #                (0)
    #              /  |  \
    #             /   |   \
    #            /    |    \
    #         (1)    (2)    (3)
    #        / | \  / | \  / | \
    #        4 5 6  7 8 9 10 11 12
    tree = Node(0,
                [Node(1, [Node(4), Node(5), Node(6)]),
                  Node(2, [Node(7), Node(8), Node(9)]),
                  Node(3, [Node(10), Node(11), Node(12)])])
    print('preorder traversal:', end='\t\t')
    for x in tree.pre_order_iter():
        print(x, end=' ')
    print('')
    print('postorder traversal:', end='\t')
    for x in tree.post_order_iter():
        print(x, end=' ')