traversals.cpp

/*
Tree Traversal Patterns
Mathematical Foundation: Visit nodes in specific order
DFS: Preorder (root→left→right), Inorder (left→root→right), Postorder (left→right→root)
BFS: Level by level using queue
Time: O(n), Space: O(h) for DFS, O(w) for BFS
*/

#include <bits/stdc++.h>
using namespace std;

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

// Inorder Traversal (Iterative)
// LeetCode: 94. Binary Tree Inorder Traversal
// https://leetcode.com/problems/binary-tree-inorder-traversal/
// Related:
// 144. Binary Tree Preorder Traversal
// https://leetcode.com/problems/binary-tree-preorder-traversal/
// 145. Binary Tree Postorder Traversal
// https://leetcode.com/problems/binary-tree-postorder-traversal/
// 173. Binary Search Tree Iterator
// https://leetcode.com/problems/binary-search-tree-iterator/
// 230. Kth Smallest Element in a BST
// https://leetcode.com/problems/kth-smallest-element-in-a-bst/
// 98. Validate Binary Search Tree
// https://leetcode.com/problems/validate-binary-search-tree/
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    while (root || !st.empty()) {
        while (root) {
            st.push(root);
            root = root->left;
        }
        root = st.top(); st.pop();
        res.push_back(root->val);
        root = root->right;
    }
    return res;
}

// Preorder Traversal (Iterative)
// LeetCode: 144. Binary Tree Preorder Traversal
// https://leetcode.com/problems/binary-tree-preorder-traversal/
// Related:
// 94. Binary Tree Inorder Traversal
// https://leetcode.com/problems/binary-tree-inorder-traversal/
// 145. Binary Tree Postorder Traversal
// https://leetcode.com/problems/binary-tree-postorder-traversal/
// 589. N-ary Tree Preorder Traversal
// https://leetcode.com/problems/n-ary-tree-preorder-traversal/
// 255. Verify Preorder Sequence in Binary Search Tree
// https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
// 331. Verify Preorder Serialization of a Binary Tree
// https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
vector<int> preorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> res;
    stack<TreeNode*> st; st.push(root);
    while (!st.empty()) {
        root = st.top(); st.pop();
        res.push_back(root->val);
        if (root->right) st.push(root->right);
        if (root->left) st.push(root->left);
    }
    return res;
}

// Postorder Traversal (Iterative)
// LeetCode: 145. Binary Tree Postorder Traversal
// https://leetcode.com/problems/binary-tree-postorder-traversal/
// Related:
// 94. Binary Tree Inorder Traversal
// https://leetcode.com/problems/binary-tree-inorder-traversal/
// 144. Binary Tree Preorder Traversal
// https://leetcode.com/problems/binary-tree-preorder-traversal/
// 590. N-ary Tree Postorder Traversal
// https://leetcode.com/problems/n-ary-tree-postorder-traversal/
// 543. Diameter of Binary Tree
// https://leetcode.com/problems/diameter-of-binary-tree/
// 124. Binary Tree Maximum Path Sum
// https://leetcode.com/problems/binary-tree-maximum-path-sum/
vector<int> postorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> res;
    stack<TreeNode*> st; st.push(root);
    while (!st.empty()) {
        root = st.top(); st.pop();
        res.push_back(root->val);
        if (root->left) st.push(root->left);
        if (root->right) st.push(root->right);
    }
    reverse(res.begin(), res.end());
    return res;
}

// Level Order Traversal (BFS)
// LeetCode: 102. Binary Tree Level Order Traversal
// https://leetcode.com/problems/binary-tree-level-order-traversal/
// Related:
// 107. Binary Tree Level Order Traversal II
// https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
// 103. Binary Tree Zigzag Level Order Traversal
// https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
// 429. N-ary Tree Level Order Traversal
// https://leetcode.com/problems/n-ary-tree-level-order-traversal/
// 637. Average of Levels in Binary Tree
// https://leetcode.com/problems/average-of-levels-in-binary-tree/
// 515. Find Largest Value in Each Tree Row
// https://leetcode.com/problems/find-largest-value-in-each-tree-row/
vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

// Maximum Depth
// LeetCode: 104. Maximum Depth of Binary Tree
// https://leetcode.com/problems/maximum-depth-of-binary-tree/
// Related:
// 111. Minimum Depth of Binary Tree
// https://leetcode.com/problems/minimum-depth-of-binary-tree/
// 559. Maximum Depth of N-ary Tree
// https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
// 110. Balanced Binary Tree
// https://leetcode.com/problems/balanced-binary-tree/
// 543. Diameter of Binary Tree
// https://leetcode.com/problems/diameter-of-binary-tree/
// 1339. Maximum Product of Splitted Binary Tree
// https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/
int maxDepth(TreeNode* root) {
    return !root ? 0 : 1 + max(maxDepth(root->left), maxDepth(root->right));
}

// Validate BST
// LeetCode: 98. Validate Binary Search Tree
// https://leetcode.com/problems/validate-binary-search-tree/
// Related:
// 94. Binary Tree Inorder Traversal
// https://leetcode.com/problems/binary-tree-inorder-traversal/
// 230. Kth Smallest Element in a BST
// https://leetcode.com/problems/kth-smallest-element-in-a-bst/
// 501. Find Mode in Binary Search Tree
// https://leetcode.com/problems/find-mode-in-binary-search-tree/
// 700. Search in a Binary Search Tree
// https://leetcode.com/problems/search-in-a-binary-search-tree/
// 938. Range Sum of BST
// https://leetcode.com/problems/range-sum-of-bst/
bool isValidBST(TreeNode* root) {
    function<bool(TreeNode*, long, long)> dfs = [&](TreeNode* node, long mn, long mx) {
        return !node || (mn < node->val && node->val < mx && 
                        dfs(node->left, mn, node->val) && 
                        dfs(node->right, node->val, mx));
    };
    return dfs(root, LONG_MIN, LONG_MAX);
}

// Diameter of Binary Tree
// LeetCode: 543. Diameter of Binary Tree
// https://leetcode.com/problems/diameter-of-binary-tree/
// Related:
// 124. Binary Tree Maximum Path Sum
// https://leetcode.com/problems/binary-tree-maximum-path-sum/
// 687. Longest Univalue Path
// https://leetcode.com/problems/longest-univalue-path/
// 1245. Tree Diameter
// https://leetcode.com/problems/tree-diameter/
// 104. Maximum Depth of Binary Tree
// https://leetcode.com/problems/maximum-depth-of-binary-tree/
// 110. Balanced Binary Tree
// https://leetcode.com/problems/balanced-binary-tree/
int diameterOfBinaryTree(TreeNode* root) {
    int res = 0;
    function<int(TreeNode*)> dfs = [&](TreeNode* node) {
        if (!node) return 0;
        int l = dfs(node->left), r = dfs(node->right);
        res = max(res, l + r);
        return 1 + max(l, r);
    };
    dfs(root);
    return res;
}

// Path Sum
// LeetCode: 112. Path Sum
// https://leetcode.com/problems/path-sum/
// Related:
// 113. Path Sum II
// https://leetcode.com/problems/path-sum-ii/
// 437. Path Sum III
// https://leetcode.com/problems/path-sum-iii/
// 666. Path Sum IV
// https://leetcode.com/problems/path-sum-iv/
// 124. Binary Tree Maximum Path Sum
// https://leetcode.com/problems/binary-tree-maximum-path-sum/
// 129. Sum Root to Leaf Numbers
// https://leetcode.com/problems/sum-root-to-leaf-numbers/
bool hasPathSum(TreeNode* root, int sum) {
    return root && ((!root->left && !root->right && root->val == sum) ||
                   hasPathSum(root->left, sum - root->val) ||
                   hasPathSum(root->right, sum - root->val));
}