The concept of "maintaining" a data structure involves preserving its inherent properties during operations. For instance, maintaining a monotonic queue ensures specific elements are removed during push and pop operations to keep the queue's monotonic order.

Core Concepts of Binary Trees

Types of Binary Trees:

1. Full Binary Tree: Eveery node has either 0 or 2 children. The total number of nodes in a full binary tree of depth k (starting from 1) is 2^k - 1.
2. Complete Binary Tree: All levels except possibly the last are completely filled, and all node in the last level are as far left as possible.
3. Binary Search Tree (BST): For any node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. This property enables O(log n) average-case search time. The structure is not fixed, but the element ordering must satisfy left < parent < right.
4. Balanced Binary Search Tree (e.g., AVL Tree): A BST where the height difference between the left and right subtrees of any node is at most 1. This guarantees O(log n) time complexity for insertion, deletion, and search operations. Standard Template Library (STL) containers like map, set, multimap, and multiset are typically implemented using balanced BSTs.

Storage Methods:

1. Linked Representation: Each node contains data and pointers to its left and right children.
2. Array Representation: Nodes are stored in an array. For a node at index i, its left child is at index 2*i + 1 and its right child at 2*i + 2.

Traversal Methods:

• Depth-First Search (DFS): Includes pre-order (parent, left, right), in-order (left, parent, right), and post-order (left, right, parent) traversals. These can be implemented recursively or iteratively.
• Breadth-First Search (BFS): Level-order traversal, typically implemented iteratively using a queue.

Basic Node Structure in C++:

struct TreeNode {
    int value;
    TreeNode* leftChild;
    TreeNode* rightChild;
    TreeNode(int val) : value(val), leftChild(nullptr), rightChild(nullptr) {}
};

Pre-order Traversal (Parent, Left, Right)

Recursive Implementation:

class Solution {
public:
    void preorderDFS(TreeNode* node, vector<int>& output) {
        if (node == nullptr) return;
        output.push_back(node->value);
        preorderDFS(node->leftChild, output);
        preorderDFS(node->rightChild, output);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> traversalResult;
        preorderDFS(root, traversalResult);
        return traversalResult;
    }
};

Iterative Implementation Using a Stack:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> traversalResult;
        if (root == nullptr) return traversalResult;
        stack<TreeNode*> nodeStack;
        nodeStack.push(root);
        while (!nodeStack.empty()) {
            TreeNode* currentNode = nodeStack.top();
            nodeStack.pop();
            traversalResult.push_back(currentNode->value);
            if (currentNode->rightChild) nodeStack.push(currentNode->rightChild);
            if (currentNode->leftChild) nodeStack.push(currentNode->leftChild);
        }
        return traversalResult;
    }
};

Post-order Traversal (Left, Right, Parent)

Recursive Implementation:

class Solution {
public:
    void postorderDFS(TreeNode* node, vector<int>& output) {
        if (node == nullptr) return;
        postorderDFS(node->leftChild, output);
        postorderDFS(node->rightChild, output);
        output.push_back(node->value);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> traversalResult;
        postorderDFS(root, traversalResult);
        return traversalResult;
    }
};

Iterative Implementation: This method first processes nodes in a Parent, Right, Left order using a stack, then reverses the result to acheive Left, Right, Parent order.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> traversalResult;
        if (root == nullptr) return traversalResult;
        stack<TreeNode*> nodeStack;
        nodeStack.push(root);
        while (!nodeStack.empty()) {
            TreeNode* currentNode = nodeStack.top();
            nodeStack.pop();
            traversalResult.push_back(currentNode->value);
            if (currentNode->leftChild) nodeStack.push(currentNode->leftChild);
            if (currentNode->rightChild) nodeStack.push(currentNode->rightChild);
        }
        reverse(traversalResult.begin(), traversalResult.end());
        return traversalResult;
    }
};

In-order Traversal (Left, Parent, Right)

Recursive Implementation:

class Solution {
public:
    void inorderDFS(TreeNode* node, vector<int>& output) {
        if (node == nullptr) return;
        inorderDFS(node->leftChild, output);
        output.push_back(node->value);
        inorderDFS(node->rightChild, output);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> traversalResult;
        inorderDFS(root, traversalResult);
        return traversalResult;
    }
};

Iterative Implementation:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> traversalResult;
        stack<TreeNode*> nodeStack;
        TreeNode* current = root;
        while (current != nullptr || !nodeStack.empty()) {
            if (current != nullptr) {
                nodeStack.push(current);
                current = current->leftChild;
            } else {
                current = nodeStack.top();
                nodeStack.pop();
                traversalResult.push_back(current->value);
                current = current->rightChild;
            }
        }
        return traversalResult;
    }
};

Level-order Traversal (Breadth-First Search)

This traversal visits nodes level by level using a queue. The size of the queue at the start of each level determines how many nodes to process for that level.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        queue<TreeNode*> nodeQueue;
        nodeQueue.push(root);
        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);
            }
            result.push_back(currentLevel);
        }
        return result;
    }
};