C++ In Practice - Tree Traversals BSTs

Tree Traversal & Binary Search Trees (C++11 Deep Dive)

Trees are non-linear data structures. Unlike arrays (contiguous memory), tree nodes are typically scattered across the heap, linked by pointers. This results in poor cache locality but allows for flexible, hierarchical data organization.

Data Structure & Memory Layout

Didactic Definition (Raw Pointers): Most online coding platforms (LeetCode) use raw pointers.

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

Modern C++11 Architecture (Smart Pointers): In a safety-critical production environment, we model ownership strictly. A node owns its children.

#include <memory>

struct Node {
    int val;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Note: For the algorithms below, for simplicity, we will use the Raw Pointer definition, but keep ownership in mind.

---

1. Inorder Traversal (Iterative)

Pattern: Left -> Node -> Right.

Use Case: Returns values in sorted order for BSTs.

Complexity: Time O(N) | Space O(H) (H = Height).

Under the Hood: Recursion uses the OS stack. Iterative approaches use std::stack on the heap. In deep trees (skewed, H=N), recursion risks Stack Overflow. The iterative approach is safer for arbitrary depths.

#include <vector>
#include <stack>

std::vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr != nullptr || !st.empty()) {
        // 1. Go Left as far as possible
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }

        // 2. Process Node
        curr = st.top();
        st.pop();
        result.push_back(curr->val);

        // 3. Go Right
        curr = curr->right;
    }
    return result;
}

---

2. Level Order Traversal (BFS)

Pattern: Layer by Layer.

Use Case: Network broadcasting, finding shallowest nodes.

Container: std::queue.

C++11 Optimization: We track levelSize to distinguish between tree levels without using a secondary queue.

#include <vector>
#include <queue>

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    
    std::vector<std::vector<int>> result;
    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size(); // Snapshot current level count
        std::vector<int> currentLevel;
        currentLevel.reserve(levelSize); // Optimization: Prevent reallocations

        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(std::move(currentLevel)); // Move vector to avoid copy
    }
    return result;
}

---

3. Validate Binary Search Tree (BST)

Problem: Ensure left < node < right for all descendants.

Trap: Checking only immediate children is insufficient.

Solution: Pass valid range (min, max) down the recursion.

C++11 Logic: Using long long or TreeNode* pointers for min/max allows handling INT_MIN and INT_MAX within the tree without overflow or ambiguity.

#include <climits>

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, nullptr, nullptr);
    }

private:
    // Using pointers to represent "infinity" (null means no limit)
    bool validate(TreeNode* node, TreeNode* minNode, TreeNode* maxNode) {
        if (!node) return true;

        // Constraint Check
        if ((minNode && node->val <= minNode->val) || 
            (maxNode && node->val >= maxNode->val)) {
            return false;
        }

        // Recurse:
        // Left child: Max allowed is current node
        // Right child: Min allowed is current node
        return validate(node->left, minNode, node) && 
               validate(node->right, node, maxNode);
    }
};

---

4. Lowest Common Ancestor (BST)

Problem: Find LCA of p and q.

Property: In a BST, the LCA is the node where p and q diverge (one is smaller, one is larger), or one matches the current node.

Complexity: Time O(H) | Space O(1).

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // Iterative approach is O(1) space, unlike recursion O(H)
    TreeNode* current = root;
    
    while (current) {
        if (p->val < current->val && q->val < current->val) {
            // Both targets are to the left
            current = current->left;
        } else if (p->val > current->val && q->val > current->val) {
            // Both targets are to the right
            current = current->right;
        } else {
            // Split point found (or current is one of the nodes)
            return current;
        }
    }
    return nullptr;
}

---

5. Invert Binary Tree

Problem: Mirror the tree.

Implementation: Simple Swap.

#include <algorithm> // for std::swap

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;

    // Standard C++ swap utility
    std::swap(root->left, root->right);

    invertTree(root->left);
    invertTree(root->right);
    return root;
}

---

6. Serialize and Deserialize

Problem: Convert tree to string and back.

Approach: Preorder (DFS) with Sentinel for nulls.

Stream Processing: C++ stringstream is the ideal tool for parsing space/comma-delimited strings.

#include <string>
#include <sstream>
#include <queue>

class Codec {
public:
    // Encodes a tree to a single string.
    std::string serialize(TreeNode* root) {
        if (!root) return "X"; // X denotes null
        // Format: "val,left,right"
        return std::to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(std::string data) {
        std::stringstream ss(data);
        return buildTree(ss);
    }

private:
    TreeNode* buildTree(std::stringstream& ss) {
        std::string segment;
        // Read up to the next comma
        if (!std::getline(ss, segment, ',')) return nullptr;

        if (segment == "X") return nullptr;

        TreeNode* node = new TreeNode(std::stoi(segment));
        node->left = buildTree(ss);
        node->right = buildTree(ss);
        return node;
    }
};

---

7. Kth Smallest Element in BST

Pattern: Inorder Traversal = Sorted Order.

Optimization: We don't need to store the whole vector. We just iterate and decrement k.

int kthSmallest(TreeNode* root, int k) {
    std::stack<TreeNode*> stack;
    TreeNode* curr = root;

    while (curr || !stack.empty()) {
        while (curr) {
            stack.push(curr);
            curr = curr->left;
        }

        curr = stack.top();
        stack.pop();

        // Process Node
        k--;
        if (k == 0) return curr->val;

        curr = curr->right;
    }
    return -1; // Should not reach here if k is valid
}

---

8. Construction: Preorder and Inorder

Problem: Rebuild unique tree from traversals.

Logic:

1. Preorder first element is always Root.
2. Find Root in Inorder.
3. Left of Root in Inorder is Left Subtree.
4. Right of Root in Inorder is Right Subtree.

#include <vector>
#include <unordered_map>

class Solution {
    std::unordered_map<int, int> inorderMap;
    int preorderIndex = 0;

public:
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        // Hash map for O(1) lookup of indices in inorder array
        for (int i = 0; i < inorder.size(); ++i) {
            inorderMap[inorder[i]] = i;
        }
        return arrayToTree(preorder, 0, preorder.size() - 1);
    }

    TreeNode* arrayToTree(std::vector<int>& preorder, int left, int right) {
        if (left > right) return nullptr;

        int rootVal = preorder[preorderIndex++];
        TreeNode* root = new TreeNode(rootVal);

        // Split point in inorder array
        int mid = inorderMap[rootVal];

        // Recursively build children
        // Boundaries are defined by the inorder array indices
        root->left = arrayToTree(preorder, left, mid - 1);
        root->right = arrayToTree(preorder, mid + 1, right);

        return root;
    }
};

Summary of Tree Operations

Operation	BST Complexity (Avg)	BST Complexity (Worst)	Key Logic
Search	O(log N)	O(N)	Binary decision: go left or right.
Insert	O(log N)	O(N)	Find null leaf position, attach node.
Delete	O(log N)	O(N)	If 2 children, swap with successor, delete successor.
Validate	O(N)	O(N)	Check range (min, max) recursively.
LCA	O(H)	O(N)	Find split point.

---

STL Binary Search Trees: std::set and std::map

In production C++ and for algorithmic problems requiring a "black box" sorted container, you never implement a BST manually. You use the Associative Containers.

The C++ Standard mandates that these containers have O(\log N) complexity for insertion, deletion, and search. To achieve this, implementations (GCC libstdc++, Clang libc++, MSVC) universally use Red-Black Trees (a type of self-balancing BST).

The STL BST Family

1. std::set<T>: A balanced BST of unique keys.
2. std::map<K, V>: A balanced BST of Key-Value pairs (ordered by Key).
3. std::multiset<T>: Balanced BST allowing duplicate keys.
4. std::multimap<K, V>: Balanced BST allowing duplicate keys.

---

Deep Dive: std::set vs. Manual BST

Feature	Manual TreeNode*	std::set / std::map
Structure Access	Full access (left, right)	Encapsulated. No pointer access.
Balancing	None (Degrades to O(N))	Red-Black Tree (Strict O(\log N))
Traversal	Manual (In/Pre/Post/Level)	In-order only (via Iterators)
Memory	Fragmented Heap Nodes	Fragmented Heap Nodes (Node-based)
Use Case	Tree Manipulation Problems	Fast Lookups, Range Queries, Ordering

1. Internal Representation (Red-Black Tree)

A std::set node typically looks like this under the hood:

struct _Rb_tree_node {
    _Rb_tree_color _M_color; // RED or BLACK
    _Rb_tree_node* _M_parent;
    _Rb_tree_node* _M_left;
    _Rb_tree_node* _M_right;
    T _M_value_field;
};

Because the STL handles the rebalancing (rotations, color flips), you are guaranteed worst-case O(\log N).

2. Key Operations using STL

If a problem asks "Find the smallest number greater than target" (Ceiling), do not write a BST. Use std::set::lower_bound.

Important: Always use the member function set.lower_bound(val), not the generic algorithm std::lower_bound(set.begin(), set.end(), val).

• Member: O(\log N) (Tree traversal).
• Generic: O(N) (Linear iterator advancement, though comparisons are logarithmic).

#include <set>
#include <iostream>

void stlTreeOperations() {
    std::set<int> bst = {10, 20, 30, 40, 50};

    // 1. Search O(log N)
    auto it = bst.find(30);
    if (it != bst.end()) { /* Found */ }

    // 2. Ceiling (Smallest element >= val)
    // Target: 35. Result: 40.
    auto ceiling = bst.lower_bound(35); 
    if (ceiling != bst.end()) std::cout << *ceiling; 

    // 3. Floor (Largest element <= val)
    // Target: 35. Result: 30.
    // upper_bound returns > val (40). Decrement to get <= val.
    auto floor = bst.upper_bound(35);
    if (floor != bst.begin()) {
        floor--; 
        std::cout << *floor;
    }

    // 4. In-order Traversal
    // Iterating a set produces sorted output.
    for (int val : bst) {
        std::cout << val << " "; // 10 20 30 40 50
    }
}

3. Limitations (The "Why not always?" question)

You cannot use STL containers for problems that require:

1. Structure Modification: "Invert a binary tree", "Prune branches shorter than K".
2. Subtree Metadata: "Count nodes in the left subtree of X" (STL nodes don't store subtree sizes).
3. LCA (Lowest Common Ancestor): You cannot query parent pointers or traverse up efficiently without specific iterators, and calculating LCA on a standard std::set is not directly supported via API.

---

Problem Solving with STL Trees

Scenario: "Find the Kth smallest element in a dynamic stream of numbers."

• Manual: Build a BST with size augmentation in every node. O(\log N) select.
• STL std::set:
  • Insertion: O(\log N).
  • Find Kth: std::advance(it, k). This is O(K), not O(\log N), because STL sets don't store subtree counts (Ranking).
  • Verdict: STL is suboptimal here if K \approx N.

Scenario: "Check if an array contains values i and j such that |i - j| <= t and indices are within k." (Contains Duplicate III).

• Solution: Use std::set to maintain a sliding window of size k.
• Use lower_bound to find elements in range [num - t, num + t].

#include <vector>
#include <set>
#include <cmath>

bool containsNearbyAlmostDuplicate(std::vector<int>& nums, int k, int t) {
    std::set<long long> window; // Use long long to avoid overflow during addition

    for (int i = 0; i < nums.size(); ++i) {
        long long n = nums[i];

        // 1. Check if we have a value in range [n - t, n + t]
        // We look for smallest value >= n - t
        auto it = window.lower_bound(n - t);

        // Check if that value is also <= n + t
        if (it != window.end() && *it <= n + t) {
            return true;
        }

        // 2. Add current to window
        window.insert(n);

        // 3. Maintain window size k
        if (window.size() > k) {
            window.erase(nums[i - k]);
        }
    }
    return false;
}

Summary: When to use what?

Requirement	Use Manual TreeNode*	Use std::set / std::map
Problem Type	"Invert", "LCA", "Serialize", "Depth"	"Range Query", "Ordered Map", "Sliding Window"
Internal Access	Required (left/right pointers)	Forbidden (Encapsulated)
Order	Flexible (can be unsorted)	Strictly Sorted
Duplicates	Manual handling	multiset handles automatically
Complexity	Varies (Can be O(N))	Guaranteed O(\log N)