Remember:

• Upper and Lower Bound

//find largest <= key
auto ub = upper_bound(vals.begin(), vals.end(), key);
int mini = (ub == vals.begin()) ? -1 : *(ub-1);

//find smallest >= key
auto lb = lower_bound(vals.begin(), vals.end(), key);
int maxi = (lb == vals.end()) ? -1 : *lb;

• Inorder traversal on Binary Search Tree gives Sorted order
• In a BST, the ceiling of x is the smallest node ≥ x.
• In a BST, the floor of x is the largest node ≤ x.
• Kth Largest element is same as the (n-k+1)th smallest element

Binary Tree

Basic codes

#include <iostream>
#include <queue>
using namespace std;

class node{
    public:
        int data;
        node* left;
        node* right;

    node(int d){
        this -> data = d;
        right = NULL;
        left = NULL;
    }
};

node* buildTree(node *root){
    int data;
    cout << "Enter the data: ";
    cin >> data;
    cout << endl;
    
    //when we create a memory in heap block
    //we return a memory location at the same time
    root = new node(data); 

    if(data == -1) {
        return NULL;
    }

    cout << "Left of "<< data <<" " << endl;
    root -> left = buildTree(root -> left);

    
    cout << "Right of "<< data <<" " << endl;
    root -> right = buildTree(root -> right);

    return root;
}

void levelOrder(node* root){
    //print in level wise traversal
    queue<node*>q;
    q.push(root);

    while(!q.empty()){
        int size = q.size();

        for(int i=0;i<size;i++){
            node* temp = q.front();
            cout << temp -> data << " ";
            q.pop();

            if(temp -> left) q.push(temp -> left);
            if(temp -> right) q.push(temp -> right);
        }
        cout << endl;
    }
}

void buildFromLevelOrder(node* &root){
    //this turns level order inout into a tree
    cout << "Enter data for root: ";
    int data;
    cin>> data;
    root = new node(data);

    queue<node*>q;
    q.push(root);

    while(!q.empty()){
        node* temp = q.front();
        q.pop();

        int leftData;
        cout << "Enter left data for " << temp -> data <<" : ";
        cin>> leftData;

        if(leftData != -1){
            temp -> left = new node(leftData);
            q.push(temp -> left);
        }

        int rightData;
        cout << "Enter right data for " << temp -> data <<" : ";
        cin>> rightData;

        if(rightData != -1){
            temp -> right = new node(rightData);
            q.push(temp -> right);
        }
    }
}

void inorder(node* root){
		//LNR
		if(root == NULL) return;
		
		inorder(node* root -> left);
		cout << root -> value << " ";
		inorder(node* root -> left);
		
}

int main(){
    node* root = NULL;
    //buld a tree
    buildFromLevelOrder(root);

    levelOrder(root);

}

Iterative traversal (Preorder, inorder, postorder)

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    if(root == NULL) return ans;
    
    stack<TreeNode*> st;
    st.push(root);
    
    
    while(!st.empty()) {
    
    
        TreeNode* cur = st.top(); st.pop();
        ans.push_back(cur->val);
        if(cur->right) st.push(cur->right);
        if(cur->left) st.push(cur->left);
    }
    
    
    
    
    
    
    
    
    
    return ans;
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    if(root == NULL) return ans;
    
    stack<TreeNode*> st;
    TreeNode* cur = root;
    
    
    while(!st.empty() || curr) {
    
    
        while(cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();
        ans.push_back(cur->val);
        cur = cur->right;
    }
    
    
    
    
    
    
    return ans;
}

vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root == NULL) return ans;

				stack<TreeNode*>st;
				TreeNode* curr = root;
        TreeNode* last=NULL;
        
        while(!st.empty() || curr){
        
        
            if(curr){
                st.push(curr);
                curr = curr -> left;
            }
            else{ //either you are at root or right present
                TreeNode* top = st.top();
                if(top -> right && last != top -> right)
		                curr = top -> right;
                else{
                    ans.push_back(top -> val);
                    last = top;
                    st.pop();
                }
            }
        }
        return ans;
    }

Level order traversal

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == NULL) return ans;

        queue <TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int size = q.size();
            vector <int> level;

            //this step process a whole level
            for(int i=0;i<size;i++){

                TreeNode* temp = q.front();
                q.pop();

                if(temp -> left){
                    q.push(temp -> left);
                }
                if(temp -> right){
                    q.push(temp -> right);
                }
                
                level.push_back(temp -> val);

            }
            ans.push_back(level);
        }

        return ans;
    }
};

Height of a binary tree

• Height is calculated wrt node here.
• so only one node means height = 1

int height(TreeNode* node){
        if(node == NULL) return 0;
        
        int left = height(node -> left);
        int right = height(node -> right);
        
        return max(right,left) + 1;
    }

Invert a binary tree

• Basically you are creating a mirror of binary tree

class Solution {
public:
    TreeNode* solve(TreeNode* root){
        if(root == NULL) return NULL;

        //we are standing on a node
        TreeNode* temp = new TreeNode(root -> val);
        temp -> left = solve(root -> right);
        temp -> right = solve(root -> left);

        return temp;
    }

    TreeNode* invertTree(TreeNode* root) {
        TreeNode* ans = solve(root);

        return ans;
    }
};

Binary tree is balanced or not? (using pair approach)

• Note: this worked because null tree (root == NULL) is considered to be a balanced tree
• Basic approach: the tree is balanced if it’s left and right subtrees are balanced and the abs height diff of any node is ≤1

class Solution {
public:
    pair<bool,int>balanced(TreeNode* root){
        if(root == NULL) return {true, 0};

        pair<bool,int> left = balanced(root -> left);
        pair<bool,int> right = balanced(root -> right);

        //process the height
        int hei = max(left.second, right.second) + 1;
        //process the bool
        bool diff = abs(left.second - right.second) <= 1 ;

        if(left.first && right.first && diff) return {true,hei};
        else return {false,hei};
    }
    bool isBalanced(TreeNode* root) {
        return balanced(root).first;
    }
};

Diameter of a binary tree (using pair)

• *** Diameter is the longest path between any two nodes ***
• 3 Possibilities: left subtree, right subtree, both included; return the max
• Optimized approach:

class Solution {
public:
    pair <int,int> diameterFast(TreeNode* root){
		    // <height, diameter>
        //base case
        if(root == NULL){
            return {0,0};
        }

				//fetch information from left and right
        pair <int,int> left = diameterFast(root -> left);
        pair <int,int> right = diameterFast(root -> right);

        //we need to store the current height
        int hei = max(left.first, right.first) + 1;

        //we need to store the diameter
        int leftDia = left.second;
        int rightDia = right.second;
        int midDia = left.first + right.first;

        int dia = max(midDia, max(leftDia, rightDia));

        //returning them
        return {hei, dia};
    }
    int diameterOfBinaryTree(TreeNode* root) {
        return diameterFast(root).second;
    }
};

• Using Recursion for better understanding (with proper breakdown)

class Solution {
public:
    int height(TreeNode* node){
        //base
        if(node == NULL) return 0;
        
        int left = height(node -> left);
        int right = height(node -> right);
        
        return max(right,left) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        //base case
        if(root == NULL) return 0;
        
        int leftDia = diameterOfBinaryTree(root -> left);
        int rightDia = diameterOfBinaryTree(root -> right);
        
        int midDia = height(root -> left) + height(root -> right);
        
        return max(max(leftDia,rightDia), midDia);
    }
};

Maximum Path Sum

Intuition:

1. At each node, the maximum path sum can be either:
   • Through the node: left subtree + node + right subtree
   • Going up to parent: node + max(left, right)
2. Ignore negative paths — they only reduce the sum.
3. Use recursion to compute max path sum for children, and keep a global variable to track the overall maximum.

class Solution {
public:
    int maxPathSumUtil(TreeNode* root, int& maxPath){
        if(root == NULL) return 0;

        //0 just to ignore the negative values
        int left = max (0, maxPathSumUtil(root -> left, maxPath));
        int right = max(0, maxPathSumUtil(root -> right, maxPath));

				// Update the maximum path sum that passes through the current node
        maxPath = max(maxPath, root -> val + left + right);        

        return root -> val + max(left, right); //going up to the parents
    }

    int maxPathSum(TreeNode* root) {
        int maxPath = INT_MIN;
        maxPathSumUtil(root, maxPath);
        return maxPath;
    }
};

Checking of tree are identical

class Solution {
  public:
    // Function to check if two trees are identical.
    bool isIdentical(Node *r1, Node *r2) {
        if(r1 == NULL && r2 == NULL) return true;
        if(r1 == NULL || r2 == NULL) return false;
        if(r1->data != r2->data) return false;
        return isIdentical(r1->left, r2->left) && isIdentical(r1->right, r2->right);
    }
};

ZigZag Traversal of binary tree

class Solution{
    public:
    //Function to store the zig zag order traversal of tree in a list.
    vector <int> zigZagTraversal(Node* root)
    {
    	vector<int> result;
    	if(root == NULL){
    	    return result;
    	}
    	
    	queue<Node*>q;
    	q.push(root);
    	
    	bool leftToRight = true;
    	
    	while(!q.empty())
    	{
    	    int size = q.size();
    	    vector<int> ans(size);
    	    
    	    //process the level
    	    for(int i=0;i<size;i++){
    	        Node* temp = q.front();
                q.pop();    	        
    	        
    	        int index = leftToRight ? i : size - i - 1;
    	        ans[index] = temp -> data;
    	        
    	        if(temp -> left) q.push(temp -> left);
    	        if(temp -> right) q.push(temp -> right);
    	        
    	    }
    	    
    	    for(auto i : ans){
    	        result.push_back(i);
    	    }
    	    leftToRight = !leftToRight;
    	    
    	}
    	return result;
    }
};

Boundary traversal

Intuition:

The code performs boundary traversal of a binary tree by dividing the problem into three parts:

1. Left Boundary (excluding leaves) – Traverse top-down along the leftmost path, adding only non-leaf nodes.
2. Leaves – Traverse the entire tree and add all leaf nodes in left-to-right order.
3. Right Boundary (excluding leaves) – Traverse bottom-up along the rightmost path, adding only non-leaf nodes.

Finally, the root is added first, and the results of these three traversals are combined to form the complete boundary sequence.

class Solution {
  public:
    void leftTraversal(Node *root, vector<int>& ans){
        if(root == NULL) return;
        
        //if leaf then return
        if(root -> left == NULL && root -> right == NULL) return;
        
        //othewise
        ans.push_back(root -> data);
        
        //go left if exist, otherwise right
        if(root -> left) leftTraversal(root -> left, ans);
        else leftTraversal(root -> right, ans);
    }
    
    void leafTraversal(Node *root, vector<int>& ans){
        //inorder traversal
        if(root == NULL) return;
        
        //if we are in a root we will store and return
        if(root -> left == NULL && root -> right == NULL){
            ans.push_back(root->data);
            return;
        }
        
        leafTraversal(root->left,ans);
        leafTraversal(root->right,ans);
        
    }
    void rightTraversal(Node *root, vector<int>& ans){
        if(root == NULL) return;
        
        //if root then return
        if(root -> left == NULL && root -> right == NULL) return;
        
        //keep going right if exist, otherwise go left
        if(root -> right) rightTraversal(root -> right, ans);  
        else rightTraversal(root -> left, ans);  
        
        //just to understand: we go deeper first then print while returning
        ans.push_back(root -> data);
    }
    
    vector<int> boundaryTraversal(Node *root) {
        
        vector<int> ans;
        if(root == NULL) return ans;
        
        ans.push_back(root -> data); //store root first
        
        //starting from left child of the root
        leftTraversal(root -> left, ans);
        
        //left subtree leaf
        leafTraversal(root -> left, ans);
        //right subtree leaf
        leafTraversal(root -> right, ans);
        
        //starting from right child of the root
        rightTraversal(root -> right, ans);
        
        return ans;
        
    }
};

Vertical Traversal

• You are just going to fill “nodes” wrt to the hd and level

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, map<int, multiset<int>>> nodes;  // hd -> level -> sorted node values
        queue<pair<TreeNode*, pair<int,int>>> q;  // node, {hd, level}
        vector<vector<int>> ans;

        if (!root) return ans;

        q.push({root, {0, 0}});

        while (!q.empty()) {
            auto [node, pos] = q.front(); q.pop();
            int hd = pos.first, lvl = pos.second;

            nodes[hd][lvl].insert(node->val);

            if (node->left)  q.push({node->left,  {hd - 1, lvl + 1}});
            if (node->right) q.push({node->right, {hd + 1, lvl + 1}});
        }

        for (auto& [hd, lvlMap] : nodes) {
            vector<int> col;
            for (auto& [lvl, vals] : lvlMap)
                col.insert(col.end(), vals.begin(), vals.end());
            ans.push_back(col);
        }

        return ans;
    }
};

Top view of a binary tree

class Solution {
  public:
    // Function to return a list of nodes visible from the top view
    // from left to right in Binary Tree.
    vector<int> topView(Node *root) {
        // maps hd and data
        // we only record the first node encountered for a specific hd
        map<int, int>  nodes;
        
        vector<int> ans;
        if(root == NULL) return ans;
        
        //queue that stores the pair == node its hd
        queue<pair<Node*, int > >  q;
        
        //push the root into the queue
        q.push(make_pair(root,0));
        
        while(!q.empty()){
            auto temp = q.front();
            q.pop();
            
            //now access the node
            Node* tempNode = temp.first;
            int hd = temp.second;
            
            // if the horizontal distance is not recorded, insert it
            if(nodes.find(hd) == nodes.end())
            nodes[hd] = tempNode -> data;
            
            //next left node
            if(tempNode -> left)
                q.push(make_pair(tempNode -> left, hd-1));
                
            //next right node
            if(tempNode -> right)
                q.push(make_pair(tempNode -> right, hd+1));
        }
        
        //now extract the answers from the ds nodes
        for(auto& i : nodes){
            ans.push_back(i.second);
        }
        return ans;
    }
};

Bottom View

Just remove the following condition, so that the node for a specific Horizontal distance will get updated as we go lower, hence giving the lowest node for a specific Horizontal distance

						if(nodes.find(hd) == nodes.end())
            nodes[hd] = tempNode -> data;
            
            // to 
            
            nodes[hd] = tempNode -> data;

Left View

• Main concept is that: you take only one node from one level

make the following changes in the TOP VIEW code

• replace hd → lvl
• replace hd-1 and hd+1 by lvl+1

to solve it using recursion

class Solution {
  public:
    void left_view(Node* root, int lvl, vector<int>& ans){
        //base case
        if(root == NULL) return;
        
        //true is we just entered into a new level
        if(ans.size() == lvl) ans.push_back(root -> data);
        
        left_view(root -> left, lvl+1, ans);
        left_view(root -> right, lvl+1, ans);
    }
    vector<int> leftView(Node *root) {
        vector<int> ans;
        int lvl = 0;
        
        left_view(root, lvl, ans);
        
        return ans;
    }
};

Right View

Make the changes in the LEFT VIEW Code

						if(nodes.find(lvl) == nodes.end())
            nodes[lvl] = tempNode -> data;
            
            // to 
            
            nodes[lvl] = tempNode -> data;

Print Node to root path

bool solve(TreeNode<int> *root, int x, vector<int>&ans){
	if(root == NULL) return false;

	ans.push_back(root -> data);
	if(root -> data == x) return true; //you found the node, dont go any down
	
	bool left = solve(root -> left, x, ans);
	bool right = solve(root -> right, x, ans);
	if(left || right) return true;
	ans.pop_back();
	return false;
}

vector<int> pathInATree(TreeNode<int> *root, int x)
{
    vector<int> ans;
	solve(root, x, ans);
	return ans;
}

LCA in Binary tree

Three Cases arises:

1. if both are null, ret null
2. if both aren’t null ret root
3. if one of them is not null, ret that one

Or, in other words:

1. if (null, null) return null;
2. if (match, null) return match;
3. if (match, match) ret root;

class Solution {
public:
    TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
		    //base case
        if(root == NULL) return NULL;
        if(root == p || root == q) return root;

        TreeNode* left = lca(root-> left, p, q);
        TreeNode* right = lca(root-> right, p, q);

        if(left && right) return root; //match, match
        else return left ? left : right; //match, null
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        return lca(root, p, q);
    }
};

Maximum Width of Binary Tree

Definition: the number of nodes in a level between any 2 nodes

• the left and right child of a node have the idx = 2idx+1 and 2idx+2 resp. if its a 0 based indexing

The concept of offset in it:

• Think of left as the starting point of the level, and you measure all other nodes relative to it. right is how far the last node is from the start.

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(root == NULL) return 0; // Edge case: empty tree has width 0

        // Queue for BFS: stores pair of (node, index)
        // Index is the position of the node if the tree were a complete binary tree
        queue<pair<TreeNode*, int>> q;
        q.emplace(root, 0); // Root node has index 0

        int ans = 0; // To store the maximum width

        while(!q.empty()){
            int size = q.size(); // Number of nodes at current level

            // 'left' is the index of the first node at this level
            unsigned long long left = q.front().second;
            unsigned long long right = left; // Initialize right as left

            for(int i = 0; i < size; i++){
                auto node = q.front().first; // Current node
                // Normalize index by subtracting 'left' to prevent large numbers
                unsigned long long idx = q.front().second - left;
                q.pop();

                right = idx; // Keep updating right to last node's normalized index

                // Push left and right children into queue with their "virtual" indices
                if(node->left) q.emplace(node->left, 2*idx + 1);
                if(node->right) q.emplace(node->right, 2*idx + 2);
            }

            // Width of this level = right - left + 1
            // Since we normalized left to 0, width = right - 0 + 1 = right + 1
            ans = max(ans, (int)right - 0 + 1);
        }

        return ans; // Return maximum width among all levels
    }
};

Check Sum Tree

• also known as children sum property
• A Sum Tree is a binary tree in which the value of each node is equal to the sum of the values of its left and right subtrees.
• Approach is same as Balanced BT

class Solution {
  public:
  
    pair <bool,int> fastSum(Node* root){
			  //<isSumTree, sum>
        //base case
        if(root == NULL) return {true, 0};
        if(root -> left == NULL && root -> right == NULL) return {true,root -> data};
        
        //get the ans from left and right
        pair <bool,int> leftSum = fastSum(root -> left);
        pair <bool,int> rightSum = fastSum(root -> right);
        
        //process the sum and bool
        int sum = leftSum.second + rightSum.second;
        bool checkSum = leftSum.first && rightSum.first;
        
        if(sum == root->data && checkSum) return {true, sum + root-> data};
        else return {false, sum};
    }
    bool isSumTree(Node* root) {
        return fastSum(root).first;
    }
};

• Change any binary tree to Children Sum Property

void changeTree(BinaryTreeNode < int > * root) {
    if(root == NULL) return ;

    int sum = 0;
    if(root -> left) sum += root -> left -> data;
    if(root -> right) sum += root -> right -> data;

    if(root -> data <= sum) root -> data = sum;
    else{
        if(root -> left) root -> left -> data = root -> data;
        if(root -> right) root -> right -> data = root -> data;
    }

    changeTree(root -> left);
    changeTree(root -> right);

    sum = 0;
    if(root -> left) sum += root -> left -> data;
    if(root -> right) sum += root -> right -> data;
    if(root -> left || root -> right) root -> data = sum;
}

Nodes at Distance k

• Return all the nodes are at a distance k from the given distance
• you need to have the flexibility to go upward, so store parent node; use level order traversal to map child to parent
• once you reach the target, do dfs and increase distance and once distance = k, store the node

class Solution {
public:
    void dfs(TreeNode* root, int k, vector<int>& ans, unordered_map<TreeNode*, bool>& vis, unordered_map<TreeNode*,TreeNode*>& parent) {
        if(root == NULL || vis[root]) return;

        //mark the current node as visited
        vis[root] = true;

        if(k == 0){ ans.push_back(root -> val); return; }

        //try all direction: child
        if(root -> left) dfs(root -> left, k-1, ans, vis, parent);
        if(root -> right) dfs(root -> right, k-1, ans, vis, parent);
        //now try the parent: make sure it not the actual root
        if(parent.count(root)) dfs(parent[root], k-1, ans, vis, parent);
    }
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        //step 1: create parent
        unordered_map<TreeNode*,TreeNode*> parent;
        queue<TreeNode*>q;
        q.push(root);

        while(!q.empty()){
            int size = q.size();

            for(int i=0;i<size;i++){
                auto node = q.front(); q.pop();

                //parent mapped
                if(node -> left) parent[node -> left] = node, q.push(node -> left);
                if(node -> right) parent[node -> right] = node, q.push(node -> right);
            }
        }

        vector<int> ans;
        unordered_map<TreeNode*, bool> vis;
        dfs(target, k, ans, vis, parent);
        return ans;
    }
};

Minimum Time to Burn a Tree from a Node

• Build parent links (since each node already knows its children but not its parent).
• Find the start node where infection begins.
• Do a BFS from that node — at each minute, infection spreads to all uninfected neighbors (left, right, and parent).
• The number of BFS levels = total time needed to infect the entire 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) {}
 * };
 */
class Solution {
public:
    int amountOfTime(TreeNode* root, int start) {
        TreeNode* target = NULL;
        unordered_map<TreeNode*, TreeNode*> parent;
        queue <TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int size = q.size();
            for(int i=0;i<size;i++){
                auto node = q.front(); q.pop();

                if(node -> val == start) target = node; //store the address of the start node

                if(node -> left) parent[node -> left] = node, q.push(node -> left);
                if(node -> right) parent[node -> right] = node, q.push(node -> right);
            }
        }

        //do bfs using it
        unordered_map<TreeNode*, bool> burnt;
        burnt[target] = true;
        int time = 0;
        q.push(target);
        while(!q.empty()){
            int size = q.size();
            bool flag = 0; //flag keep the track if atleast one node is burnt or not, say a node having burnt adjacent will also cause time++ if flag is not maintained

            for(int i=0;i<size;i++){
                auto node = q.front(); q.pop();
                burnt[node] = true;
                if(node -> left && !burnt[node -> left]) q.push(node -> left), flag = 1;
                if(node -> right && !burnt[node -> right]) q.push(node -> right), flag = 1;
                if(parent.count(node) && !burnt[parent[node]]) q.push(parent[node]), flag = 1;
            }
            if(flag)time++;
        }
        return time;
    }
};

Count Nodes of Complete BT

• In less than o(N)

Steps :

1. calculate the right height
2. calculate the left height
3. if they are equal: ret the no. of nodes equivalent to that in Perfect BT ie 2^height - 1
4. else return 1 + left recursion + right recursion

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == NULL) return 0;

        TreeNode* temp = root;
        int lh = 0;
        while(temp){
            lh++; temp = temp -> left;
        }
        temp = root;
        int rh = 0;
        while(temp){
            rh++; temp = temp -> right;
        }

        if(lh == rh) return (1 << lh) - 1;
        return 1 + countNodes(root -> left) + countNodes(root -> right);
    }
};

To Create a Unique Binary Tree

• We need anything with Inorder Binary tree, may it be post or preorder
• Inorder is Important

Construct BinaryTree from Inorder and Preorder

class Solution {
  public:
    // Function to build the tree from given inorder and preorder traversals
    int findIdx(vector<int> &inorder, int element){
        for(int i=0;i<inorder.size();i++){
            if(inorder[i] == element) return i;
        }
        return -1;
    }
    
    Node* solve(vector<int> &inorder, vector<int> &preorder, int s, int e, int& idx){
        if(idx >= inorder.size() || s>e) return NULL;
        
        //make a root
        int element = preorder[idx++];
        Node* root = new Node(element);
        
        //now build its left and right part
        //find position of the current node in inorder
        int pos = findIdx(inorder, element);
        root -> left = solve(inorder, preorder, s, pos-1, idx);
        root -> right = solve(inorder, preorder, pos+1, e, idx);
        
        return root;
    }
    
    Node *buildTree(vector<int> &inorder, vector<int> &preorder) {
        //since first element is the root
        int preIndex = 0;
        
        //inorder start and end index
        int s = 0;
        int e = inorder.size() - 1;
        
        Node* ans = solve(inorder, preorder, s, e, preIndex);
        return ans;
    }
};

• Little concise version

class Solution {
public:
    TreeNode* solve(vector<int>& preorder, vector<int>& inorder, int s, int e, int& idx, unordered_map<int, int>&inMap){
        if(idx >= preorder.size() || s > e) return NULL;

        int val = preorder[idx++];
        TreeNode* root = new TreeNode(val);
        int pos = inMap[val];

        root -> left = solve(preorder, inorder, s, pos-1, idx, inMap);
        root -> right = solve(preorder, inorder, pos+1, e, idx, inMap);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int preIdx = 0;
        
        int s = 0;
        int e = inorder.size();

        unordered_map<int, int>inMap;
        for(int i=0;i<inorder.size();i++) inMap[inorder[i]] = i;

        return solve(preorder, inorder, s, e, preIdx, inMap);
    }
};

Construct BT from In-order and Post-order

• with small changes in prev qs, you can achieve this:
  • you traverse postorder from n-1 to 0, in reverse (LRN ←)
  • you create the right child before the left child (LRN ←)

class Solution {
public:
    TreeNode* solve(vector<int>& postorder, vector<int>& inorder, int s, int e, int& idx, unordered_map<int, int>&inMap){
        if(idx < 0 || s > e) return NULL;

        int val = postorder[idx--];
        TreeNode* root = new TreeNode(val);
        int pos = inMap[val];

        // you are traversing the LRN in reverse in postorder, so you make the right node first
        root -> right = solve(postorder, inorder, pos+1, e, idx, inMap);
        root -> left = solve(postorder, inorder, s, pos-1, idx, inMap);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int postIdx = postorder.size() - 1;
        
        int s = 0;
        int e = inorder.size() - 1;

        unordered_map<int, int>inMap;
        for(int i=0;i<inorder.size();i++) inMap[inorder[i]] = i;

        return solve(postorder, inorder, s, e, postIdx, inMap);
    }
};

Serialize and desterilize BT

#include <string>
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s = "";
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int size = q.size();
            for(int i=0;i<size;i++){
                auto node = q.front(); q.pop();
                
                if(node) s.append(to_string(node -> val) + ',');
                else s.append("#,");

                //if the node is not null, then you push the children
                if(node) q.push(node -> left), q.push(node -> right); 
            }
        }
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream s(data);
        string str;
        getline(s, str, ','); //str has the first value string
        if(str.empty() || str == "#") return NULL;

        TreeNode* root = NULL;
        root = new TreeNode(stoi(str));

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            auto node = q.front(); q.pop();

            getline(s, str, ',');
            if(str.empty() || str == "#") node -> left = NULL;
            else node -> left = new TreeNode(stoi(str)), q.push(node -> left);

            getline(s, str, ',');
            if(str.empty() || str == "#") node -> right = NULL;
            else node -> right = new TreeNode(stoi(str)), q.push(node -> right);
        }

        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

Morris In-order Traversal

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root){
        vector<int> ans;
        TreeNode* curr = root;

        while(curr != NULL){
            //Left child DNE then store curr and move right
            if(curr -> left == NULL){
                ans.push_back(curr->val);
                curr = curr->right;
            }
            //left child exist then
            else{
                TreeNode* prev = curr -> left;

                //findout rightmost node of left subtree, might be null or pointig to curr
                while(prev -> right && prev -> right != curr){
                    prev = prev -> right;
                }

                //after this we are in the last node

                //if null, we create a thread, and curr is moved to left
                if(prev -> right == NULL){
                    prev -> right = curr;
                    curr = curr -> left;
                }
                //otherwsie, if thread exist(pointing to curr), means we traversed all in left
                //so remove thread, store curr val, and move curr to right
                else{
                    prev -> right = NULL;
                    ans.push_back(curr -> val);
                    curr = curr -> right;
                }
            }
        }
        return ans;

    }
};

Morris Preorder Traversal

• Change wrt morris preorder w push is done if the right most node of the LST is null

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* curr = root;
        vector<int> ans;

        while(curr != NULL){
            if(curr -> left == NULL){
                ans.push_back(curr -> val);
                curr = curr -> right;
            }
            else{
                TreeNode* prev = curr -> left;

                while(prev -> right && prev -> right != curr){
                    prev = prev -> right;
                }

                if(prev -> right == NULL){
                    prev -> right = curr;
                    ans.push_back(curr -> val); //change: push is shifted here!
                    curr = curr -> left;
                }
                else{
                    prev -> right = NULL;
                    curr = curr -> right;
                }
            }
        }
        return ans;
    }
};

Flatten a Binary Tree to Linked List

• if left child exist
  • store it in prev
  • then take prev to the rightmost node
  • link the rightmost node to right node of current
  • link the left child of current as the next child in the LL
  • nullify the curr left
• update the current to right child
• repeat the process till current is null

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* curr = root;

        while(curr!=NULL){
            if(curr -> left != NULL){
                TreeNode* prev = curr -> left;

                while(prev -> right){
                    prev = prev -> right;
                }

                prev -> right = curr -> right;
                curr -> right = curr -> left;
                curr -> left = NULL;
            }
            curr = curr ->right;
        }
    }
};

Binary tree to DLL

Here head is the node that is passed on as the first node of the list, and prev is the one that is given as a representator of a converted dll for linking

class Solution {
  public:
    void solve(Node* root, Node*& head, Node*& prev){
        if(root == NULL) return;
        
        solve(root -> left, head, prev);
        
        //so basically prev has the node of the dll
        //which is just converted and need to be linked
        //so prev just pass on the node that needs to be link
        //prev is representator of the "just made" dll
        if(prev == NULL) head = root;
        else{
            prev -> right = root;
            root -> left = prev;
        }
        prev = root;
        
        solve(root -> right, head, prev);
    }
    
    Node* bToDLL(Node* root) {
        Node* head = NULL, *prev = NULL;
        solve(root, head, prev);
        
        return head;
    }
};

OR

class Solution {
  public:
    Node* inorder(Node* root) {
        if (root == NULL) return NULL;
        
        Node* lst = inorder(root->left);
        if (lst) {
            while (lst->right) lst = lst->right; // Move to the rightmost node of left subtree
            lst->right = root;
            root->left = lst;
        }
        
        Node* rst = inorder(root->right);
        if (rst) {
            while (rst->left) rst = rst->left; // Move to the leftmost node of right subtree
            root->right = rst;
            rst->left = root;
        }

        // Move to the leftmost node (DLL head)
        Node* head = root;
        while (head->left) head = head->left;
        return head;
    }

    Node* bToDLL(Node* root) {
        return inorder(root);
    }
};

String to binary tree e.g 4()()

Step by step approach:

1. Maintain a single index that traverses through the string from left to right.
2. When encountering digits, parse them to form the complete node value and create a new node with the parsed value.
3. If an opening parenthesis ‘(‘ is found, increment index and recursively build left subtree. After left subtree is built and index is incremented past closing parenthesis, check for another opening parenthesis.
4. If second opening parenthesis exists, increment index and recursively build right subtree.
5. Return the constructed node which serves as root for its subtree

class Solution{
public:
    Node* solve(string& s, int& i){
        if(s[i] == ')') return NULL;
        
        int val = 0;
        while(i < s.length() && s[i] != '(' && s[i] != ')'){
            int digit = s[i] - '0';
            i++;
            val = val*10 + digit;
        }
        
        Node* root = new Node(val);
        
        if(i < s.length() && s[i] == '('){
            i++;
            root -> left = solve(s,i);
            i++;
        }
        
        if(i < s.length() && s[i] == '('){
            i++;
            root -> right = solve(s,i);
            i++;
        }
        
        return root;
    }
    
    
    Node *treeFromString(string str){
        int i =0;
        return solve(str,i);
    }
};

Sum of nodes on the longest path

class Solution {
  public:
    void bloodline(Node* root, int sum, int &maxSum, int len, int &maxLen){
        //base case
        if(root == NULL){
            if(len > maxLen){
                maxLen = len;
                maxSum = sum;
            }
            else if(len == maxLen){
                maxSum = max(maxSum, sum);
            }
            return;
        }
        
        sum += root -> data;
        
        bloodline(root -> left, sum, maxSum, len+1, maxLen);
        bloodline(root -> right, sum, maxSum, len+1, maxLen);
    }
    int sumOfLongRootToLeafPath(Node *root) {
        int maxLen = 0;
        int maxSum = INT_MIN;
        
        bloodline(root, 0, maxSum, 0, maxLen);
        
        return maxSum;
    }
};

K Path sum (no. of paths having the sum k)

class Solution {
  public:
  
    void solve(Node *root, int k, vector<int>& path, int& count){
        //base case
        if(root == NULL) return;
        
        //imagine we are standing on a random node
        
        //we have to push the node into the array
        path.push_back(root -> data);
        
        //check the sum by taking nodes one by one from behind
        //we increase the count if we find
        int size = path.size();
        int sum=0;
        for(int i=size-1;i>=0;i--){
            sum+=path[i];
            if(sum == k) count++;
        }
        
        //now go deeper
        solve(root->left, k, path, count);
        solve(root->right, k, path, count);
        
        //we have to pop since we go upward
        path.pop_back();
    }
    int sumK(Node *root, int k) {
        int count = 0;
        vector<int> path;
        solve(root, k, path, count);
        
        return count;
    }
};

Kth ancestor of a node in a binary tree

Node* kSolve(Node *root, int& k, int node){
    if(root == NULL) return NULL;
    
    if(root->data == node) return root;
    
    Node* left = kSolve(root->left, k, node);
    Node* right = kSolve(root->right, k, node);
    
    if(left || right){
        k--;
        if(k == 0) return root;
        return left ? left : right;
    }
    
    return NULL;
}

int kthAncestor(Node *root, int k, int node) {
    Node* ans = kSolve(root, k, node);
    return (ans && ans->data != node) ? ans->data : -1;
}

Maximum of non adjacent nodes

class Solution{
  public:
    //Function to return the maximum sum of non-adjacent nodes.
    pair<int, int> solve(Node* root){
        //base case
        if(root == NULL) return make_pair(0,0);
        
        int include = 0;
        int exclude = 0;
        
        pair<int, int> left = solve(root -> left);
        pair<int, int> right = solve(root -> right);
        
        exclude = max(left.second, left.first) + max(right.first, right.second);
        include = root -> data + left.second + right.second;
        
        return make_pair(include, exclude);
    }
    
    int getMaxSum(Node *root) 
    {
        pair<int,int>ans = solve(root);
        return max(ans.first, ans.second);
    }
};

Binary Search Tree

Insertion into BST

#include <iostream>
using namespace std;

class Node{
    public:
    int data;
    Node* left;
    Node* right;

    Node(int data){
        this -> data = data;
        this -> left = NULL;
        this -> right = NULL;
    }
};

void insertToBST(Node*& root, int data){
    //base case
    if(root == NULL){
        root = new Node(data);
        return;
    }
    
    if(data > root -> data){
        insertToBST(root -> right, data);
    }
    else{
        insertToBST(root -> left, data);
    }
}

void preorder(Node* root){
    if(root == NULL) return;

    cout << root -> data << " ";
    preorder(root -> left);
    preorder(root -> right);
}

int main(){
    Node* root = NULL;
    int data;
    cin >> data;
    while(data != -1){
        insertToBST(root, data);
        cin >> data;
    }

    preorder(root);
}

• Iterative Approach

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL) return new TreeNode(val);
        TreeNode* curr  = root;
        while(true){
            //go right
            if(curr -> val < val){
                if(curr -> val == NULL){
                    curr -> right = new TreeNode(val);
                    break;
                }
                else curr = curr -> right;
            }
            else{
                if(curr -> left == NULL){
                    curr -> left = new TreeNode(val);
                    break;
                }
                else curr = curr -> left;
            }
        }

        return root;
    }
};

Deletion of Node

• just use the regular searching algo
• once you find the node
• there are 4 cases:

1. no child: just dlt
2. one child (left): just replace the current node with the child
3. one child (right): just replace the current node with the child
4. two child: you have two choices, you can either fetch the largest data from lst, or the smallest from rst, then replace the current node value with the ftched one and just call recursively deleteNode for the last node to be deleted from either the lst or rst

/*
    🧠 Binary Search Tree (BST) Deletion — Case-based Approach
    ---------------------------------------------------------
    For a node to be deleted, there are 3 cases:

    1️⃣ No child (leaf node)           → return NULL.
    2️⃣ One child (left or right)      → return that child.
    3️⃣ Two children                   → 
        - Find the inorder successor (smallest node in right subtree)
        - Copy its value to current node
        - Recursively delete the successor
*/

class Solution {
public:
    // 🔹 Helper to find the minimum node (inorder successor)
    TreeNode* findMin(TreeNode* root) {
        while (root->left) 
            root = root->left;
        return root;
    }

    // 🔹 Main recursive delete function
    TreeNode* deleteNode(TreeNode* root, int key) {
        // Base case: empty tree
        if (!root) return NULL;

        // Traverse the tree to find the node to delete
        if (key < root->val) 
            root->left = deleteNode(root->left, key);      // go left
        else if (key > root->val) 
            root->right = deleteNode(root->right, key);    // go right
        else {
            // 🎯 Found the node to delete

            // Case 1: No left or right child
            if (!root->left && !root->right) 
                return NULL;

            // Case 2: One child
            else if (!root->left) 
                return root->right;
            else if (!root->right) 
                return root->left;

            // Case 3: Two children
            else {
                // Find inorder successor (smallest in right subtree)
                TreeNode* successor = findMin(root->right);

                // Copy its value to current node
                root->val = successor->val;

                // Delete the inorder successor recursively
                root->right = deleteNode(root->right, successor->val);
            }
        }
        return root;
    }
};

• Helper Function approach:

class Solution {
public:
    // 🔹 Helper function to restructure the tree after deletion
    TreeNode* helper(TreeNode* root) {
        // Case 1: No left child → return right child
        if (root->left == NULL) 
            return root->right;

        // Case 2: No right child → return left child
        else if (root->right == NULL) 
            return root->left;

        // Case 3: Node has both children
        TreeNode* rightChild = root->right;    // Save right subtree
        TreeNode* leftChild = root->left;      // Save left subtree

        // Find the rightmost node of the left subtree
        while (leftChild->right) 
            leftChild = leftChild->right;

        // Attach the right subtree to the rightmost node of the left subtree
        leftChild->right = rightChild;

        // Return the new subtree root (the original left child)
        return root->left;
    }

    // 🔹 Main function to delete a node with given key
    TreeNode* deleteNode(TreeNode* root, int key) {
        // Base case: empty tree
        if (root == NULL) 
            return NULL;

        // Special case: root itself is the node to be deleted
        if (root->val == key) 
            return helper(root);

        TreeNode* current = root;  // Pointer to traverse the tree

        // Traverse until we find the parent of the node to be deleted
        while (current) {
            // Case A: key lies in the left subtree
            if (key < current->val) {
                // If left child is the target node, delete it using helper
                if (current->left && current->left->val == key) {
                    current->left = helper(current->left);
                    break;  // Deletion done
                } 
                else {
                    current = current->left;
                }
            }

            // Case B: key lies in the right subtree
            else {
                // If right child is the target node, delete it using helper
                if (current->right && current->right->val == key) {
                    current->right = helper(current->right);
                    break;  // Deletion done
                } 
                else {
                    current = current->right;
                }
            }
        }

        // Return original root (in case it's unchanged)
        return root;
    }
};

How this code works: [Key = 3]

      5
     / \
    3   6
   / \   \
  2  4    7

1. find 3
2. connect 5.left and 2
3. find

Ceil in a Binary Search Tree

• Alternate approach: can also be done by sorting
• Ceil: The smallest number ≥ key

int findCeil(BinaryTreeNode<int> *node, int x){
    if(node == NULL) return -1;
    int ceil = -1;
    while(node){
        if(node -> data == x) return x; //exact match
        //condition matched, store and check for smaller
        else if(node -> data > x) ceil = node -> data, node = node -> left;
        //not matched, try increasing the value 
        else node = node -> right;
    }
    return ceil;
}

Floor in BST

• Floor = The greatest number ≤ key

int floorInBST(TreeNode<int> * root, int x)
{
    if(root == nullptr) return -1;
    int floor = -1;
    while(root){
        if(root -> val == x) return x;
        else if(root -> val < x) floor = root -> val, root = root -> right;
        else root = root -> left;
    }
    return floor;
}

Kth Smallest element is BST

• Inorder gives element in a sorted fashion, so this helps
• To find the kth largest element, you need to find the (n-k+1)the smallest element
• Alternative Its a less intuitive approach but you can do reverse-inorder like: RNL

class Solution {
public:
    int solve(TreeNode* root, int& i, int k){
        if(root == NULL) return -1;

        //left
        int left = solve(root -> left, i, k);
        if(left != -1) return left;

        //Node
        i++;
        if(i == k) return root -> val;

        //right
        return solve(root -> right, i, k);
    }

    int kthSmallest(TreeNode* root, int k) {
        int i=0;
        return solve(root, i, k);
    }
};

Validate BST

bool solve(TreeNode* root, long min, long max) {
    if (!root) return true;
    if (root->val > min && root->val < max) {
        return solve(root->left, min, root->val) && solve(root->right, root->val, max);
    }
    return false;
}

bool isValidBST(TreeNode* root) {
    return solve(root, LONG_MIN, LONG_MAX);
}

LCA in BST

Three Cases Arises: say for LCA(5,9)

***[ Do a check if the current node is one of (p,q) or not, if so that node is our ans, since one node appears before another means it is lying above the other ] → handled by

1. Both of them lie on the right side of the current node
2. Both of them lie on the left side
3. The first node for which they split or if any other case apart from the above 2 (which covers the one given in ***), is our ans!

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) return NULL;

        //whenever you see both of them are on different side, that node is our ans
        while(root){
            if(root -> val == p -> val || root -> val == q -> val) return root;
            
            if(p -> val < root -> val && q -> val < root -> val) root = root -> left;
            else if(p -> val > root -> val && q -> val > root -> val) root = root -> right;
            else return root; //this handles the case 
        }
        return NULL;
    }
};

Construct BST from PreOrder

• Sort it, you’ll get the inorder [but this is less efficient]

• Here in the most optimized code you need to maintain an upper bound

• Root: you can create a node only if the value is less than upper bound

• Left: when you traverse left, ub = current node value

• Right: When you traverse right, ub = ub, ie you maintain the ub

class Solution {
public:
    TreeNode* bst(vector<int>& preorder, int& i, int ub){
        if(i >= preorder.size() || preorder[i] > ub) return NULL;

        TreeNode* root = new TreeNode(preorder[i++]);
        root -> left = bst(preorder, i, root -> val);
        root -> right = bst(preorder, i, ub);

        return root;
    }
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        int ub = INT_MAX;
        int i = 0;
        return bst(preorder, i, ub);
    }
};

Predecessor and successor in BST

pair<int, int> predecessorSuccessor(TreeNode* root, int key) {
    int pre = -1, suc = -1;
    TreeNode* curr = root;

    // Find the key and track potential predecessor and successor
    while (curr && curr->data != key) {
        if (key < curr->data) {
            suc = curr->data;
            curr = curr->left;
        } else {
            pre = curr->data;
            curr = curr->right;
        }
    }

    if (!curr) return {pre, suc};

    // Predecessor: max value in left subtree
    TreeNode* temp = curr->left;
    while (temp) {
        pre = temp->data;
        temp = temp->right;
    }

    // Successor: min value in right subtree
    temp = curr->right;
    while (temp) {
        suc = temp->data;
        temp = temp->left;
    }

    return {pre, suc};
}

Recover BST

• Two of the nodes will be swapped incorrectly, you need to res-wap to recover BST

class Solution {
    TreeNode* prev;
    TreeNode* first;
    TreeNode* middle;
    TreeNode* last;

public:
    void inorder(TreeNode* root){
        if(root == NULL) return;

        inorder(root -> left);

        if(prev && prev -> val > root -> val){
            //first violation
            if(first == NULL){
                first = prev;
                middle = root;
            }
            //second violation
            else{
                last = root;
            }
        }

        prev = root;
        inorder(root -> right);
    }

    void recoverTree(TreeNode* root) {
        first = middle = last = NULL;
        prev = new TreeNode(INT_MIN);
        inorder(root);

        //if second violation never occured, its adjacent case
        if(last == NULL) swap(first -> val, middle -> val);
        else swap(first -> val, last -> val); //otherwise its a swap b/w non adjacents
    }
};

Largest BST in BT***

• Normal binary tree will be given, find the largest BST within it
• Used tuple here, you can use struct as well
• Condition for BST:
  • (largest from left) < node < (smallest from right)
  • Both Left and Right sides are BST individually

class Solution {
    
  public:
    
    tuple<int, int, int, bool, int> solve(Node *root){
        //size, max, min, isBST, ans(ie the final ans returning from root)
        if(root == NULL) return {0, INT_MIN, INT_MAX, true, 0};
        //if its a leaf node
        if(root -> left == NULL && root -> right == NULL) return {1, root -> data, root -> data, true, 1};
        
        
        //do a postorder travesal, fetch the left and right info
        auto [lSize, lMax, lMin, lBst, lAns] = solve(root -> left);
        auto [rSize, rMax, rMin, rBst, rAns] = solve(root -> right);
        
        //node operation now
        //check if its a bst?
        bool flag1 = lMax < root -> data && root -> data < rMin;
        bool flag2 = lBst && rBst; //both side bst or not
        
        if(flag1 && flag2){
		        //current part is a bst
		        int currSize = 1+ lSize + rSize;
		        int maxi = max({lMax, rMax, root -> data});
		        int mini = min({lMin, rMin, root -> data});
		        
		        return {currSize, maxi, mini, true, currSize};
        }
        else{
		        int ans = max(lAns, rAns); //current part isn't bst, so get the max ans from either side
			      
			      return {0, INT_MAX, INT_MIN, false, ans};
				}
    }
    
    int largestBst(Node *root) {
        //bst when: (largest from left) < node < (smallest from right)
        auto [size, maxi, mini, isBst, ans] = solve(root);
        return ans;
    }
};

Flatten BST into LL

void inorder(vector<int>& inArr, TreeNode<int>* root){
    if(root == NULL) return;

    inorder(inArr, root -> left);
    inArr.push_back(root -> data);
    inorder(inArr, root -> right);
}

TreeNode<int>* flatten(TreeNode<int>* root)
{
    vector<int> inArr;
    inorder(inArr, root);

    TreeNode<int>* newRoot = new TreeNode<int> (inArr[0]);
    TreeNode<int>* curr = newRoot;

    for(int i=1;i<inArr.size();i++){
        TreeNode<int>* temp = new TreeNode<int> (inArr[i]);
        curr -> right = temp;
        curr = temp;
    }

    return newRoot;
}

Normal BST to Binary BST

void inorder(TreeNode<int>* root, vector<int>& inArr){
    if(root == NULL) return;

    inorder(root -> left, inArr);
    inArr.push_back(root -> data);
    inorder(root -> right, inArr);
}

TreeNode<int>* solve(vector<int> inArr, int s, int e){
    if(s>e) return NULL;

    int mid = (s+e)/2;

    int data = inArr[mid];
    TreeNode<int>* temp = new TreeNode<int> (data);
    temp -> left = solve(inArr, s, mid-1);
    temp -> right = solve(inArr, mid+1, e);

    return temp;
}

TreeNode<int>* balancedBst(TreeNode<int>* root) {
    vector<int> inArr;
    inorder(root,inArr);

    int s = 0;
    int e = inArr.size()-1;

    return solve(inArr, s, e);
}

Building BST from preorder

BinaryTreeNode<int>* solve(vector<int> &preorder, int mini, int maxi, int& i){
    if(i>=preorder.size()) return NULL;

    if(preorder[i] < mini || preorder[i] > maxi) return NULL;

    BinaryTreeNode<int>* temp = new BinaryTreeNode<int> (preorder[i++]);
    temp -> left = solve(preorder, mini, temp -> data, i);
    temp -> right = solve(preorder, temp -> data, maxi, i);

    return temp;
}

BinaryTreeNode<int>* preorderToBST(vector<int> &preorder) {
    int mini = INT_MIN;
    int maxi = INT_MAX;
    int i=0;

    return solve(preorder, mini, maxi, i);
}

Size of the largest BST in a Binary Tree

class info{
    public:
    int maxi;
    int mini;
    bool isBST;
    int size;
};

info solve(TreeNode * root, int& ans){
    if(root == NULL) return {INT_MIN, INT_MAX,true,0};

    info left = solve(root -> left, ans);
    info right = solve(root -> right, ans);

    info curr;
    
    curr.mini = min(root -> data, left.mini);
    curr.maxi = max(root -> data, right.maxi);

    curr.size = left.size + right.size + 1;

    bool flag = left.maxi < root -> data && right.mini > root -> data;
    if(left.isBST && right.isBST && flag) curr.isBST = true;
    else curr.isBST = false;

    if(curr.isBST) ans = max(ans, curr.size);

    return curr;
}

int largestBST(TreeNode * root){
    int maxSize =0;
    info temp = solve(root, maxSize);

    return maxSize;
}

Miscleneous

Diagoanal traversal (not working for all test case)

while going left → hd+1

while gong right → hd as it is

class Solution {
  public:
    vector<int> diagonal(Node *root) {
        map<int, vector<int>> nodes; // Stores nodes in diagonal order
        vector<int> ans;
        if(root == NULL) return ans;
        
        queue<pair<Node*, int>> q; // Stores {node, diagonal level}
        q.push({root, 0});
        
        while(!q.empty()) {
            auto temp = q.front();
            q.pop();
            
            Node* tempNode = temp.first;
            int hd = temp.second;
            
            nodes[hd].push_back(tempNode->data);
            
            if(tempNode->left)  // Move left child to next diagonal
                q.push({tempNode->left, hd+1});
            
            if(tempNode->right) // Keep right child in the same diagonal
                q.push({tempNode->right, hd});
        }
        
        // Collecting values in correct order
        for(auto &i : nodes) {
            for(auto value : i.second) {
                ans.push_back(value);
            }
        }
        return ans;
    }
};

Diagonal traversal (works fine)

• Basic approach is that:

1. you are on a node, store the value
2. check if the left exist, if yes push in a q
3. now check the right, if exist update curr into it, if don't exist check then its the end node
4. now update the curr to the front elemet of the q
5. if q is exhausted, the end

OR IN OTHER WORDS

1. keep going along the right digonal untill the end, and store all the nodes and do the following along the path
2. store the value
3. if left node exist push to the q
4. when reach the end take the front value of the q and repeat

class Solution {
  public:
    vector<int> diagonal(Node *root) {
        vector<int> ans;
        if(root == NULL) return ans;
        
        queue<Node*>q;
        q.push(root);
        
        while(!q.empty()){
            auto temp = q.front();
            q.pop();
            
            while(temp != NULL){
                //store the data
                ans.push_back(temp -> data);
                //push left child into q
                if (temp-> left) q.push(temp->left);
                //next right node
                temp = temp -> right;
            }
            
        }
        
        return ans;
    }
};