Skip to content

Instantly share code, notes, and snippets.

@zahlenteufel
Created July 8, 2015 12:50
Show Gist options
  • Save zahlenteufel/3a9a17133394d3cabe93 to your computer and use it in GitHub Desktop.
Save zahlenteufel/3a9a17133394d3cabe93 to your computer and use it in GitHub Desktop.
Iterative inorder traversal of a Binary Tree in C++11
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
struct node {
int value;
node* left;
node* right;
node(int value, node* left, node* right) {
this->value = value;
this->left = left;
this->right = right;
}
~node() {
delete this->left;
delete this->right;
}
};
node* bin(int v, node* left, node* right) {
return new node(v, left, right);
}
node* leaf(int v) {
return bin(v, NULL, NULL);
}
void visit(node* n) {
cout << n->value << endl;
}
void inorder(node* n) {
stack<pair<node*, bool> > s;
auto defer = [&](node* n) { s.push(make_pair(n, true)); };
auto call = [&](node* n) { s.push(make_pair(n, false)); };
call(n);
while (!s.empty()) {
n = s.top().first;
bool defered = s.top().second;
s.pop();
if (n == NULL)
continue;
if (!defered) {
defer(n);
call(n->left);
} else {
visit(n);
call(n->right);
}
}
}
int main() {
node* a = bin(3, bin(1, NULL, leaf(2)), bin(5, leaf(4), leaf(6)));
inorder(a);
delete a;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment