All Binary Tree Codes 23 jan:
#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;
}
};
//make a binary tree from bfs array:
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;
}
//dfs:
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 << " ";
}
//BFS:
void subBfs(vector<int> &ans, queue<TreeNode*> &q){
if(q.empty()) return;
TreeNode* temp = q.front();
q.pop();
ans.push_back(temp->val);
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
subBfs(ans, q);
return;
}
vector<int> levelOrder(TreeNode* root){
vector<int> ans;
if(root==NULL) return ans;
queue<TreeNode*> q;
q.push(root);
subBfs(ans, q);
return ans;
}
// Height of BT:
int treeHeight(TreeNode* root){
if(root == NULL) return 0;
int left = treeHeight(root->left);
int right = treeHeight(root->right);
return max(left, right) + 1;
}
// Diameter of a BT:
int treeDiameter(TreeNode* root){
if(root== NULL) return 0;
// 1. height_left + height_right + 1(root)
// 2. maxdiameter at left or right
// calculate the tree height from both sides and then return height_left + height_right + 1
int leftHeight = treeHeight(root->left);
int rightHeight = treeHeight(root->right);
int leftDiameter = treeDiameter(root->left);
int rightDiameter = treeDiameter(root->right);
return max(leftHeight+rightHeight+1, max(leftDiameter, rightDiameter));
// TC: O(N*height)
}
pair<int,int> heightDiameter(TreeNode* root){
if(root==NULL){
pair<int,int> p;
p.first = p.second = 0;
return p;
}
pair<int,int> leftAns = heightDiameter(root->left);
pair<int,int> rightAns = heightDiameter(root->right);
int lh = leftAns.first;
int ld = leftAns.second;
int rh = rightAns.first;
int rd = rightAns.second;
pair<int,int> p;
p.first = 1 + max(lh, rh);
p.second = max(lh+rh+1, max(ld, rd));
return p;
// TC = O(N)
}
// Minimum Depth of a BT:
// [ 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. Depth = 0 only when left and right both die. Skew Edge case. ]
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;
}
// Transform into Sumtree (leaf vals = 0):
int solve(TreeNode* root){
if(!root) return 0;
// pass: l + r + data
// take: l + r
int temp = root->val;
int l = solve(root->left);
int r = solve(root->right);
root->val = l + r;
return l + r + temp;
}
void toSumTree(TreeNode* root){
solve(root);
}
// Check for Sumtree (leaf vals != 0):
int help(Node* root){
if(root == NULL) return 0;
//call left and right:
int l = help(root->left);
int r = help(root->right);
if(root->data != l+r and root->left and root->right){
check = false;
}
return l + r + root->data;
}
bool isSumTree(Node* root)
{
// Your code here
check = true;
help(root);
return check;
}
// Check for Height balanced BT:
int parse(TreeNode* root, bool &check){
if(root==NULL) return 0;
int l = parse(root->left, check);
int r = parse(root->right, check);
if(abs(l-r) > 1) check = false;
return max(l, r) + 1;
}
bool isBalanced(TreeNode *root){
// Your Code here
bool check = true;
parse(root, check);
return check;
}
// Build a BST from array with a[0] as root:
void buildBST(TreeNode* root, int x){
if(root == NULL) return;
//node specific:
// check for where to go left or right?
if(x > root->val){
// go right if exists, else make new:
if(!root->right){
root->right = new TreeNode(x);
}
else buildBST(root->right, x);
}
else{
// go to left, else make new:
if(!root->left){
root->left = new TreeNode(x);
}
else buildBST(root->left, x);
}
return;
}
// Build BT from Pre 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;
// TC: O(N)
// SC: O(N)
}
// LCA of two nodes:
TreeNode* lca(TreeNode* root, int n1, int n2){
// True/False or node specfic technquie:
//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;
// TC: O(N)
}
//zig zag trvaersal:
vector<int> zigZag(TreeNode* root){
vector<int> ans;
if(!root) return ans;
int line = 0;
queue<TreeNode*> q;
q.push(root);
//simple bfs + size instance technique:
int line = 0;
while(!q.empty()){
int size = q.size();
vector<int> temp;
// for changing the direction everytime we
// need to take care of size instance:
while(size--){
TreeNode* n = q.front();
q.pop();
temp.push_back(n->val);
if(n->left) q.push(n->left);
if(n->right) q.push(n->right);
}
//pushing on the basis of dir:
if(line==0){
for(auto x: temp) ans.push_back(x);
temp.clear();
line = !line;
}
else if(line == 1){
reverse(temp.begin(), temp.end());
for(auto x: temp) ans.push_back(x);
temp.clear();
line = !line;
}
}
return ans;
// TC: O(N2)
}
vector<int> zigZagTraversal(TreeNode* root){
vector<int> ans;
if(!root) return ans;
int line = 0;
deque<TreeNode*> dq;
dq.push_front(root);
while(!dq.empty()){
int sz = dq.size();
while(sz--){
if(line == 0){
// Left to Right:
TreeNode* node = dq.front();
dq.pop_front();
ans.push_back(node->val);
// make for 2nd line:
// children will be reversed:
if(node->left) dq.push_back(node->left);
if(node->right) dq.push_back(node->right);
}
else if(line == 1){
//Right to Left:
TreeNode* node = dq.back();
dq.pop_back();
ans.push_back(node->val);
//make for children, normal --> for front:
if(node->right) dq.push_front(node->right);
if(node->left) dq.push_front(node->left);
}
}
line = !line;
}
return ans;
// TC: O(N)
}
// diagonal traversal of a Binary Tree:
vector<int> diagonal(TreeNode* root){
vector<int> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
//pointer technique:
while(!q.empty()){
TreeNode* tmp = q.front();
q.pop();
while(tmp){
// store lefts for next diagonal:
if(tmp->left) q.push(tmp->left);
// go to right:
ans.push_back(tmp->val);
tmp = tmp->right;
}
}
return ans;
}
// Max Width of a Binary Tree (**):
int treeWidth(TreeNode* root){
// observations:
// 1. for width we require start and end node and ans = diff.
// 2. for starting and ending node we will use array indexing method: 2i+1, 2i+2 + BFS.
// 3. it will keep the track with null node as well because it takes indexing from root itself.
// BFS + instance + indexingArray
if(!root) return 0;
int ans = 1;
queue<pair<TreeNode*,int>> q;
q.push({root, 0});
while(!q.empty()){
//update ans as end - start on the basis of idxs:
int start = q.front().second;
int end = q.back().second;
ans = max(ans, abs(start - end) + 1);
// size instance:
int sz = q.size();
while(sz--){
auto it = q.front();
TreeNode* n = it.first;
long long i = it.second;
q.pop();
// push left and right:
if(n->left) q.push({n->left, 2*i+1});
if(n->right) q.push({n->right, 2*i+2});
}
}
return ans;
}
// Largest Sum of a subtree:
int drive(TreeNode* root){
int sum = 0;
largestSubTreeSum(root, sum);
return sum;
}
int largestSubTreeSum(TreeNode* root, int &sum){
if(!root) return 0;
int l = largestSubTreeSum(root->left, sum);
int r = largestSubTreeSum(root->right, sum);
sum = max(sum, root->val + l + r);
return root->val + l + r;
}
// Get all possible paths of leaf from root:
vector<vector<int>> paths(TreeNode* root){
vector<vector<int>> paths;
if(!root) return paths;
vector<int> tmp;
help(root, tmp, paths);
return paths;
}
void help(TreeNode* root, vector<int> &tmp, vector<vector<int>> &paths){
if(!root) return;
//node specific:
tmp.push_back(root->val);
// get left and right:
if(root->left) help(root->left, tmp, paths);
if(root->right) help(root->left, tmp, paths);
//stop: push in final ans.
if(root->left == NULL and root->right == NULL){
paths.push_back(tmp);
}
// backtrack:
tmp.pop_back();
return;
}
// root to node X path:
vector<int> root2node(TreeNode* root, TreeNode* x){
vector<int> ans;
if(!root) return ans;
help(root, x, ans);
return ans;
}
bool help(TreeNode* root, TreeNode* x, vector<int> &ans){
// True/False Technique:
if(!root) return false;
//node specific:
ans.push_back(root);
//confirm for current node:
if(root->val == x->val) return true;
// search in left and right:
bool l = help(root->left, x, ans);
bool r = help(root->right, x, ans);
if(l || r) return true;
// backtrack:
ans.pop_back();
return false;
}
// Kth Ancestor of a node in BT O(N) + O(1):
int kthAncestor(TreeNode* root, int k, int x){
// idea:
// 1. find path of x node from root
// 2. when found then backtrack and decrease k meanwhile
// 3. deliver the ans when k == 0.
int ans = -1;
help(root, x, k, ans);
return ans;
}
bool help(TreeNode* root, int x, int &k, int ans){
if(!root) return false;
if(root->val == x){
return true;
}
bool l = help(root->left, x, k, ans);
bool r = help(root->right, x, k, ans);
if(l or r){
k = k-1;
if(k == 0) ans = root->val;
return true;
}
return false;
// TC: O(N)
// SC: Stack
}
// Kth ancestor of node X in SC = O(N) + stack:
bool help(TreeNode* root, vector<int> &ans){
if(!root) return false;
ans.push_back(root->val);
if(root->val == x) return true;
if(help(root->left, ans) || help(root->right, ans)){
return true;
}
ans.pop_back();
return false;
}
int kthAncestor(TreeNode* root, int x){
vector<int> ans;
if(!root) return ans;
help(root, ans);
reverse(ans.begin(), ans.end());
return ans[k-1];
}
// tree to string (BRACKET REPRESENTATION):
string tree2String(TreeNode* root){
// Observation:
// 1. push left anyways
// 2. push right only if exists.
// 3. dont push if both dont exists.
if(!root) return "";
string ans = "";
ans += to_string(root->val);
if(root->left || root->right){
ans += "(" + tree2String(root->left) +")";
if(root->right) ans += "(" + tree2String(root->right) +")";
}
return ans;
// 1
// 2 3
// 4
// OP: "1(2()(4))(3)"
}
// Find Duplicate Subtrees(**):
unordered_map<string,int> m;
vector<int> res;
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root){
//observations:
// 1. subtrees: bracket string reprstn.
// 2. node specific.
m.clear();
res.clear();
help(root);
return res;
}
string help(TreeNode* root){
if(root == NULL) return "";
// get left and right:
string l = help(root->left);
string r = help(root->right);
// final ans:
string ans = "(" + l + to_string(root->val) + r + ")";
// update frequency:
if(m[ans] != -1) m[ans]++;
// check frequency in map:
if(m[ans] > 1){
res.push_back(root);
m[ans] = -1; // so that we dont push again and again.
}
return ans;
}
// distance of a node x from root:
int rootDistance(TreeNode* root, int x){
if(!root) return 0;
int ans = -1;
help(root, 0, x, ans);
return ans;
}
bool help(TreeNode* root, int level, int x, int &ans){
if(!root) return false;
if(root->val == x){
if(ans == -1) ans = level; //backtrack will update ans again&again
return true;
}
bool l = help(root->left, level+1, x, ans);
bool r = help(root->right, level+1, x, ans);
if(l || r){
if(ans == -1) ans = level; //backtrack will update ans again&again
return true;
}
return false;
}
// sorted array to BST with balanced height:
TreeNode* sortedArray2BST(vector<int> &arr){
// observations:
// 1. for height balanced = root should be from mid.
// 2. for again making every subtree follow (1).
if(arr.size() == 0) return NULL;
return help(arr, 0, arr.size()-1);
}
TreeNode* help(vector<int> arr, int lb, int ub){
// Soln: BINARY SEARCH.
// Try making like L r R such that L < r < R and you can do this using r as mid in binary search.
if(lb > ub) return NULL;
// calculate mid and make a new root:
int m = (lb+ub)/2;
TreeNode* root = new TreeNode(arr[m]);
// no need for left and right:
if(lb == ub) return root;
//make left and right:
root->left = help(arr, lb, m-1);
root->right = help(arr, m+1,ub);
return root;
}
// Right view of a Binary Tree:
vector<int> rightSideView(TreeNode* root){
vector<int> r;
if(!root) return r;
help(root, 0, r);
return r
}
void help(TreeNode* root, int level, vector<int> &res){
if(!root) return;
// node specific:
if(res.size() == level) res.push_back(root->val);
help(root->right, level+1, res);
help(root->left, level+1, res);
return;
}
// Left view of a Binary Tree:
vector<int> lefttSideView(TreeNode* root){
vector<int> res;
if(!root) return res;
help(root, 0, res);
return r
}
void help(TreeNode* root, int level, vector<int> &res){
if(!root) return;
// node specific:
if(res.size() == level) res.push_back(root->val);
help(root->left, level+1, res);
help(root->right, level+1, res);
return;
}
// All nodes at K distance below from root:
vector<int> kBelow(TreeNode* root, int k){
vector<int> ans;
if(!root) return ans;
queue<TreeNode*> q;
q.push(root);
int level = 0;
while(!q.empty()){
int size = q.size();
while(size--){
TreeNode* tmp = q.front();
q.pop();
if(level == k) ans.push_back(tmp);
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
level++;
}
return ans;
}
void kbelowR(TreeNode* root, vector<int> &ans, int level, int k){
if(!root || k < 0) return;
if(level == k) ans.push_back(root->val);
kbelowR(root->left, ans, level+1, k);
kbelowR(root->right, ans, level+1, k);
return;
}
// All nodes below + above at k distance from target node:
vector<int> ans;
unordered_map<TreeNode*,TreeNode*> m;
void makeParents(TreeNode* root){
// 1. Start from target.
// since we have to backtrack -> have to use parent node.
// make a seen map for parent -> so that we dont get oscillating between two child and their parent. eg. 5 <-> 3 <-> 1.
// make a map for storing parents of each node.
// keep track of each leveel for K.
if(!root) return;
// hash it:
if(root->left) m[root->left] = root;
if(root->right) m[root->right] = root;
makeParents(root->left);
makeParents(root->right);
return;
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int k){
makeParents(root);
// start appyling bfs from target with seen and hashmap:
ans.clear();
if(root == NULL) return ans;
unordered_map<TreeNode*,int> seen;
queue<TreeNode*> q;
q.push(target);
while(!q.empty()){
int sz = q.size();
for(int i=0;i<sz;i++){
TreeNode* cur = q.front();
q.pop();
//mark visited:
seen[cur] = 1;
// if level is reached:
if(k == 0) ans.push_back(cur->val);
// push parent and chidlren:
TreeNode* parent = m[cur];
if(parent and seen[parent] != 1) q.push(parent);
if(cur->left and seen[cur->left] != 1) q.push(cur->left);
if(cur->right and seen[cur->right] != 1) q.push(cur->right);
}
k--;
if(k < 0) break;
}
return ans;
}
// Flatten a Binary Tree in pre order fashion:
// left to NULL and right to next value:
void help(TreeNode* root, TreeNode* &tmp){
if(!root) return;
tmp->left = NULL;
tmp->right = root;
tmp = root;
TreeNode* l = root->left;
TreeNode* r = root->right;
// call for others:
help(l, tmp);
help(r, tmp);
return;
}
void flatten(TreeNode* root){
TreeNode* dummy = new TreeNode(-1);
TreeNode* tmp = dummy;
help(root, tmp);
tmp->left = tmp->right = 0;
return;
}
// Flatten a Binary Search Tree into Linked List in sorted manner:
//left as null and right as next pointer
void help(TreeNode* root, TreeNode* &tmp){
if(root == 0) return;
help(root->left, tmp);
tmp->left = NULL;
tmp->right = root;
tmp = root;
help(root->right, tmp);
}
void flattenBst(TreeNode* root){
TreeNode* dummy = new TreeNode(-1);
TreeNode* tmp = dummy;
help(root, tmp);
tmp->left = tmp->right = 0;
return;
}
// Flatten a Binary Tree into DLL (**)
// https://practice.geeksforgeeks.org/problems/leaves-to-dll/1#
bool help(TreeNode* root, TreeNode* &tmp){
if(!root) return false;
// if leaf: TreeNode SPECIFIC TECHNQIUE:
if(!root->left and !root->right){
tmp->right = root;
root->left = tmp;
tmp = root;
return true;
}
bool l = help(root->left, tmp);
bool r = help(root->right, tmp);
if(l) root->left = NULL;
if(r) root->right = NULL;
return false;
}
TreeNode * convertToDLL(TreeNode *root){
// add code here.
TreeNode* dummy = new TreeNode(-12);
dummy->left = NULL;
dummy->right = NULL;
TreeNode* tmp = dummy;
help(root, tmp);
tmp->right = NULL;
TreeNode* head = dummy->right;
head->left = NULL;
delete dummy;
TreeNode* prev = head;
TreeNode* cur = head->right;
while(cur){
cur->left = prev;
prev = cur;
cur = cur->right;
}
return head;
}
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_PRE(root);
return 0;
}
Comments
Post a Comment