Recursive Traversal Implementations

Perorder Traversal

Process the node's value before visiting its left and right subtrees.

void preorderTraverse(TreeNode* currentNode, vector<int>& results) {
    if (currentNode == nullptr) {
        return;
    }
    results.push_back(currentNode->value);
    preorderTraverse(currentNode->leftChild, results);
    preorderTraverse(currentNode->rightChild, results);
}

Inorder Traversal

Process the node's value between visiting its left and right subtrees.

void inorderTraverse(TreeNode* currentNode, vector<int>& results) {
    if (currentNode == nullptr) {
        return;
    }
    inorderTraverse(currentNode->leftChild, results);
    results.push_back(currentNode->value);
    inorderTraverse(currentNode->rightChild, results);
}

Postorder Traversal

Process the node's value after visiting both its left and right subtrees.

void postorderTraverse(TreeNode* currentNode, vector<int>& results) {
    if (currentNode == nullptr) {
        return;
    }
    postorderTraverse(currentNode->leftChild, results);
    postorderTraverse(currentNode->rightChild, results);
    results.push_back(currentNode->value);
}

Iterative Implementations Using a Stack

Preorder Traversal (Iterative)

Push the root onto the stack. While the stack isn't empty, pop the top node, process its value, then push its right child (if exists) followed by its left child (if exists).

void iterativePreorder(TreeNode* rootNode, vector<int>& results) {
    if (rootNode == nullptr) return;
    stack<TreeNode*> nodeStack;
    nodeStack.push(rootNode);
    while (!nodeStack.empty()) {
        TreeNode* topNode = nodeStack.top();
        nodeStack.pop();
        results.push_back(topNode->value);
        if (topNode->rightChild) {
            nodeStack.push(topNode->rightChild);
        }
        if (topNode->leftChild) {
            nodeStack.push(topNode->leftChild);
        }
    }
}

Postorder Traversal (Iterative)

A postorder traversal can be derived from a modified preorder approach. Perform a modified preorder (node, then right child, then left child) and reverse the resulting sequence.

void iterativePostorder(TreeNode* rootNode, vector<int>& results) {
    if (rootNode == nullptr) return;
    stack<TreeNode*> nodeStack;
    nodeStack.push(rootNode);
    while (!nodeStack.empty()) {
        TreeNode* topNode = nodeStack.top();
        nodeStack.pop();
        results.push_back(topNode->value);
        if (topNode->leftChild) {
            nodeStack.push(topNode->leftChild);
        }
        if (topNode->rightChild) {
            nodeStack.push(topNode->rightChild);
        }
    }
    reverse(results.begin(), results.end());
}

Inorder Traversal (Iterative)

Use a pointer to traverse nodes. While the pointer is not null or the stack is not empty: if the pointer is not null, push the current node and move to its left child; otherwise, pop from the stack, process the node's value, and move to its right child.

void iterativeInorder(TreeNode* rootNode, vector<int>& results) {
    stack<TreeNode*> nodeStack;
    TreeNode* current = rootNode;
    while (current != nullptr || !nodeStack.empty()) {
        if (current != nullptr) {
            nodeStack.push(current);
            current = current->leftChild;
        } else {
            current = nodeStack.top();
            nodeStack.pop();
            results.push_back(current->value);
            current = current->rightChild;
        }
    }
}

Level Order (Breadth-First) Traversal

Process nodes level by level using a queue. For each level, determine the number of nodes, process them, and enqueue their children.

void levelOrderTraversal(TreeNode* rootNode, vector<vector<int>>& levelResults) {
    if (rootNode == nullptr) return;
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(rootNode);
    while (!nodeQueue.empty()) {
        int levelSize = nodeQueue.size();
        vector<int> currentLevel;
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* frontNode = nodeQueue.front();
            nodeQueue.pop();
            currentLevel.push_back(frontNode->value);
            if (frontNode->leftChild) {
                nodeQueue.push(frontNode->leftChild);
            }
            if (frontNode->rightChild) {
                nodeQueue.push(frontNode->rightChild);
            }
        }
        levelResults.push_back(currentLevel);
    }
}