Binary Tree Codes #1
#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
int val;
struct TreeNode* left;
struct TreeNode* right;
TreeNode(int value){
val = value;
left = right = NULL;
}
};
TreeNode* makeTree(vector<int> arr, int i){
if(i >= arr.size()) return NULL;
TreeNode* root = new TreeNode(arr[i]);
root->left = makeTree(arr, 2*i+1);
root->right = makeTree(arr, 2*i+2);
return root;
}
void printTree_PRE(TreeNode* root){
if(root == NULL) return;
// preorder: root, left, right
cout << root->val << " ";
printTree_PRE(root->left);
printTree_PRE(root->right);
}
void printTree_IN(TreeNode* root){
if(root == NULL) return;
// preorder: left, root, right
printTree_IN(root->left);
cout << root->val << " ";
printTree_IN(root->right);
}
void printTree_POST(TreeNode* root){
if(root == NULL) return;
// preorder: left, right, root
printTree_POST(root->left);
printTree_POST(root->right);
cout << root->val << " ";
}
// same tree or not:
void parse(TreeNode* p, TreeNode* q, bool &check){
if((p && !q) || (q && !p) || (p->val != q->val)){
check = false;
return;
}
if(!p && !q) return;
if(p->left && q->left) parse(p->left, q->left, check);
else if((p->left && !q->left) || (q->left && !p->left)){
check = false;
return;
}
if(p->right && q->right) parse(p->right, q->right, check);
else if((p->right && !q->right) || (q->right && !p->right)){
check = false;
return;
}
return;
}
bool isSameTree(TreeNode* p, TreeNode* q){
if(p == NULL && q == NULL) return true;
bool check = true;
parse(p, q, check);
return check;
}
// shortest distance between root and a leaf:
// if anyone left or right is NULL then return !null only because shortest path != 0 until both right and left == NULL.
int minDepth(TreeNode* root) {
if(!root) return 0;
if(root->right == NULL && root->left != NULL){
return minDepth(root->left) + 1;
}
else if(root->left == NULL && root->right != NULL){
return minDepth(root->right) + 1;
}
else return min(minDepth(root->right), minDepth(root->left)) + 1;
}
// Build a BST:
// 1. left < node
// 2. right > node.
// 3. no duplicates.
// 4. each subtree is a BST.
void insertBST(TreeNode* root, int x){
if(x > root->val){
if(!root->right){
root->right = new TreeNode(x);
}
else insertBST(root->right, x);
}
else{
if(!root->left){
root->left = new TreeNode(x);
}
else insertBST(root->left, x);
}
return;
}
// zig zag order traversal:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
int line = 1;
while(!q.empty()){
int size = q.size();
vector<int> temp;
while(size--){
TreeNode* node = q.front();
temp.push_back(node->val);
q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
//push the temp into main vector based on line no:
if(line == 1){
ans.push_back(temp);
temp.clear();
line = !line;
}
else if(line == 0){
reverse(temp.begin(), temp.end());
ans.push_back(temp);
temp.clear();
line = !line;
}
}
return ans;
}
// check if all leaves are at same level:
//LOGIC: at same level, the height of all leaves is same i.e. their level no. is same.
// map<int,TreeNode*> m;
int lastLevel = 0;
bool gflag = true;
void parse(TreeNode* root, int level){
if(!root) return;
// the only edge case: if right and left of specific node are NULL: if first time then put otherwise false.
if(root->left == NULL && root->right == NULL){
if(level != lastLevel){
if(lastLevel) gflag = false;
else lastLevel = level;
}
return;
}
//goto bottom:
parse(root->left, level + 1);
parse(root->right, level + 1);
return;
}
bool checkLevel(TreeNode* root){
parse(root, 1);
return gflag;
}
// max sum level:
int maxLevelSum(TreeNode* root) {
map<int,int> m;
queue<pair<TreeNode*,int>> q;
q.push({root, 1});
while(!q.empty()){
auto it = q.front();
TreeNode* node = it.first;
q.pop();
int level = it.second;
m[level] += node->val;
if(node->left) q.push({node->left, level + 1});
if(node->right) q.push({node->right, level + 1});
}
int maxSum = INT_MIN;
int ans = 1;
for(auto x:m){
if(maxSum < x.second){
maxSum = x.second;
ans = x.first;
}
}
return ans;
}
// take bfs in a vector
vector<vector<int>> levelVectors(TreeNode* root){
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
//instance technique:
while(!q.empty()){
int size = q.size();
vector<int> temp;
while(size--){
TreeNode* node = q.front();
temp.push_back(node->val);
q.pop();
if(root->left) q.push(root->left);
if(root->right) q.push(root->right);
}
ans.push_back(temp);
temp.clear();
}
}
// build tree from preorder and inorder:
int idx = 0;
unordered_map<int,int> m;
// node->val, index in "in"
TreeNode* parse(vector<int>& pre, vector<int>& in, int lb, int ub){
if(lb > ub) return NULL;
//make node for current:
TreeNode* temp = new TreeNode(pre[idx++]);
//if cur_node is leaf i.e. no right and left:
if(lb == ub) return temp;
// adjust lb and ub for right and left using map in "in" :
int mid = m[temp->val];
// call for right and left:
temp->left = parse(pre, in, lb, mid - 1);
temp->right = parse(pre, in, mid + 1, ub);
return temp;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
idx = 0;
m.clear();
for(int i=0;i<inorder.size();i++) m[inorder[i]] = i;
TreeNode* root = parse(preorder, inorder, 0, preorder.size()-1);
return root;
}
// distance of a node from root:
int dist(TreeNode* root, int x){
if(!root) return -1;
int dis = -1;
// observations:
// 1. if root->val == x then return dis + 1 since dis = -1.
// 2. check for left and right subtrees = dis.
// 3. at last return dis for >= 0.
// check for left and right sub trees:
if((root->val == x) || (dis = dist(root->left, x) >= 0) || (dis = dist(root->right, x) >= 0)){
return dis + 1;
}
return dis;
}
// LCA of two nodes:
TreeNode* lca(TreeNode* root, int n1, int n2){
//observations:
// 1. Using left and right subtrees, at any root if n1 and n2 exists then return root.
// 2. if a non null node and a null is approaching to the root the return non null node.
// 3. if root == n1 || n2 then return root.
if(!root) return NULL;
if(root->val == n1 || root->val == n2) return root;
TreeNode* l = lca(root->left, n1, n2);
TreeNode* r = lca(root->right, n1, n2);
if(l && r) return root;
else if(l) return l;
else return r;
}
// min dis between two nodes:
// observations:
// 1. find pin point of the two nodes i.e. lca(a, b).
// 2. find distance of the two nodes from the pin point using distance function.
// 3. if pin point != n1 and n2: add distances.
// 4. if pin point == n1 or n2: return dist(n1 or n2).
int minDist(TreeNode* root, int n1, int n2){
//find pin point
TreeNode* point = lca(root, n1, n2);
if(point->val != n1 and point->val != n2){
int x = dist(point, n1);
int y = dist(point, n2);
return x + y;
}
else if(point == n1) return dist(point, n2);
else return dist(point, n1);
}
// to get all leaf nodes:
void parse(TreeNode* root, vector<int> &ans){
if(root->left == NULL and root->right == NULL){
ans.push_back(root->val);
return;
}
parse(root->left, ans);
parse(root->right, ans);
return;
}
vector<int> leafs(TreeNode* root){
vector<int> ans;
if(!root) return ans;
// observations:
// 1. goto bottom of the tree by left and right calls.
// 2. if node->right and left == NULL then just push it into the ans.
parse(root, ans);
return ans;
}
// get last level nodes:
vector<int> lastlevel(TreeNode* root){
vector<int> ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()){
int size = q.size();
vector<int> temp;
while(size--){
TreeNode* node = q.front();
temp.push_back(node->data);
q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
ans = temp;
temp.clear();
}
return ans;
}
// diagonal traversal:
// observations:
// 1. goto bottom right and store left in queue meanwhile.
// 2. if right == NULL then start process for q.front().
// 3. do till q.empty() is not true.
vector<int> diagonal(Node *root)
{
// your code here
vector<int> ans;
if(!root) return ans;
queue<Node*> q;
q.push(root);
while(!q.empty()){
Node* temp = q.front();
q.pop();
while(temp){
if(temp->left) q.push(temp->left);
ans.push_back(temp->data);
temp = temp->right;
}
}
return ans;
}
int main(){
// makeTree() use number of elements = 1 3 7 15 (2**h - 1)
// driver code
TreeNode* root = makeTree({1,2,3,4,5,6,7}, 0);
printTree_IN(root);
cout << endl;
// TreeNode* bstRoot = buildBST({5,1,3,4,2,7}, 0);
// printTree_IN(bstRoot);
TreeNode* newRoot = new TreeNode(5);
vector<int> v = {5,1,3,4,2,7};
for(int i=1;i<v.size();i++){
insertBST(newRoot, v[i]);
}
printTree_IN(newRoot);
return 0;
}
Comments
Post a Comment