Super binary tree template problems

Lots of binary tree problems can be solved by using recursive way. However, the iterative way is also very interesting. I’d like to summerize the iterative ways related to inorder traversal binary trees in this article.

94. Binary Tree Inorder Traversal

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        vector<TreeNode*> stk;
        auto node = root;
        while (node != nullptr || !stk.empty()){
            while (node != nullptr){
                stk.push_back(node);
                // go to left
                node = node -> left;
            }
            node = stk.back(); stk.pop_back();
            ret.push_back(node -> val);
            node = node -> right;
        }
        return ret;
        
    }
};

98. Validate Binary Search Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
const long long INF = 1ll << 32;
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        vector<TreeNode*> stk;
        auto node = root;
        long long prev = -INF ;
        while (node != nullptr || !stk.empty()){
            while (node != nullptr){
                stk.push_back(node);
                node = node -> left;
            }
            node = stk.back(); stk.pop_back();
            long long val = (long long)node -> val;
            if (val <= prev) return false;
            prev = val;
            node = node -> right;
        }
        return true;
    }
};

1932. Merge BSTs to Create Single BST

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void get_leaf(TreeNode* node, unordered_set<int>& leaf){
        if (node == nullptr) return;
        if (node -> left == nullptr && node -> right == nullptr){
            leaf.insert(node -> val);
            return;
        }
        get_leaf(node -> left, leaf);
        get_leaf(node -> right, leaf);
    }
    void merge(TreeNode* node, unordered_map<int, TreeNode*> &nodes){
        if (node == nullptr) return;
        if (node -> left == nullptr && node -> right == nullptr && nodes.find(node -> val) != nodes.end()){
            auto root = nodes[node -> val]; nodes.erase(node -> val);
            node -> left = root -> left;
            node -> right = root -> right;
        }
        merge(node -> left, nodes);
        merge(node -> right, nodes);
    }
    
    bool isValidBST(TreeNode* node){
        int prev = INT_MIN;
        if (node == nullptr) return true;
        vector<TreeNode*> stk;
        while (node != nullptr || !stk.empty()){
            while (node != nullptr){
                stk.push_back(node);
                node = node -> left;
            }
            node = stk.back(); stk.pop_back();
            int curr = node -> val;
            if (curr <= prev) return false;
            prev = curr;
            node = node -> right;
        }
        return true;  
    }
    TreeNode* canMerge(vector<TreeNode*>& trees) {
        if (trees.size() == 0) return nullptr;
        if (trees.size() == 1) return trees[0];
        unordered_map<int, TreeNode*> nodes;
        unordered_set<int> leaf;
        for (auto &tree: trees){
            get_leaf(tree, leaf);
            nodes[tree -> val] = tree;
        }
        for (auto &tree: trees){
            if (leaf.find(tree -> val) == leaf.end()){
                merge(tree, nodes);
                return nodes.size() == 1 && isValidBST(tree) ? tree : nullptr;
            }
        }
        return nullptr;
    }
};

Reference

[1] https://leetcode.com/problems/validate-binary-search-tree/discuss/32112/Learn-one-iterative-inorder-traversal-apply-it-to-multiple-tree-questions-(Java-Solution)

[2] top submission of LeetCode Weekly Contest 249