C++ binary search tree traversals
A binary search tree keeps smaller values in the left subtree and larger values in the right. A depth-first in-order traversal visits left, node, right, which yields the values in sorted order. A level-order traversal, also called breadth-first, visits all nodes of one depth before the next and uses a queue: pop a node, process it, and push its children.
C++
#include <iostream>
#include <memory>
#include <queue>
struct Node {
int value;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
explicit Node(int v) : value(v) {}
};
void insert(std::unique_ptr<Node>& root, int value) {
if (!root) {
root = std::make_unique<Node>(value);
} else if (value < root->value) {
insert(root->left, value);
} else if (value > root->value) {
insert(root->right, value);
}
}
void in_order(const Node* node) {
if (node == nullptr) {
return;
}
in_order(node->left.get());
std::cout << " " << node->value;
in_order(node->right.get());
}
void level_order(const Node* root) {
std::queue<const Node*> pending;
pending.push(root);
while (!pending.empty()) {
const Node* node = pending.front();
pending.pop();
std::cout << " " << node->value;
if (node->left) pending.push(node->left.get());
if (node->right) pending.push(node->right.get());
}
}
int main() {
std::unique_ptr<Node> root;
for (int v : {50, 30, 70, 20, 40, 60, 80}) {
insert(root, v);
}
std::cout << "in order:";
in_order(root.get());
std::cout << "\nlevel order:";
level_order(root.get());
std::cout << "\n";
}