Super binary tree template problems

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)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi