Trees

Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this C++ DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.cpp 
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
struct Node { int value; Node* left; Node* right; Node(int v, Node* l=nullptr, Node* r=nullptr): value(v), left(l), right(r) {} };
string render(Node* node) {
    if (node == nullptr) return "_";
    if (node->left == nullptr && node->right == nullptr) return to_string(node->value);
    return to_string(node->value) + "(" + render(node->left) + "," + render(node->right) + ")";
}
Node* sampleTree() {
    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}
string listString(const vector<int>& values) {
    stringstream out; out << "[";
    for (size_t i = 0; i < values.size(); i++) { if (i) out << ", "; out << values[i]; }
    out << "]"; return out.str();
}
void preorder(Node* node, vector<int>& output) { if (!node) return; output.push_back(node->value); preorder(node->left, output); preorder(node->right, output); }
int main() { vector<int> output; preorder(sampleTree(), output); cout << listString(output) << "\n"; }

Complexity

  • Time: O(n)
  • Space: O(h) recursion stack

Implementation notes

  • In C++, nodes are struct Node objects connected by raw Node* left and Node* right links; sampleTree() allocates them with nested new Node(...) calls.
  • preorder(Node* node, std::vector<int>& output) takes the current node as a raw pointer and the output vector by non-const reference, so recursive calls append into the same vector.
  • The null base case is if (!node) return;. Non-null calls push node->value, then recurse to node->left and node->right, adding normal C++ call-stack frames.
  • The trace records visit-before-children order 4, 2, 1, 3, 6, 5, 7, growing output from [] to [4, 2, 1, 3, 6, 5, 7].
  • listString(const std::vector<int>&) uses std::stringstream and a size_t loop to format the output, then std::cout << ... << "\n" prints [4, 2, 1, 3, 6, 5, 7].
  • Visible allocation is the tree nodes, output vector, and formatting buffer. The source uses raw pointers, not smart pointers, and does not show a matching delete cleanup path.
preorder Preorder records the current node before visiting left and right subtrees.