advanced-level-tree.cpp

// 🔹 1. Boundary Traversal
// Left boundary + leaf + right boundary
// 🧠 1. Mathematical Point of View

// Think of a binary tree as a connected acyclic graph 
// T=(V,E).
// We want to traverse the boundary of this tree in anti-clockwise order.
// 📌 Boundary = Union of 3 disjoint sets:
// Boundary(T)=L∪Leaves∪R
// Where:

// 🔹 1. Left Boundary (L)
// Path from root to the leftmost node
// Always prefer:
// left child > right child
// Excludes leaf nodes

// 👉 Mathematically:
//  lies on path from root to leftmost leaf (excluding leaf)
// }
// L={v∈V∣v lies on path from root to leftmost leaf (excluding leaf)}
// 🔹 2. Leaf Nodes
// Nodes with degree = 1 (except root)
// Leaves={v∈V∣deg(v)=1,v
// 
// =root}
// 🔹 3. Right Boundary (R)
// Path from root to rightmost node
// Prefer:
// right child > left child
// Excludes leaf nodes
// Added in reverse order
// 👉 Mathematically:
//  lies on path from root to rightmost leaf (excluding leaf)
// }
// R={v∈V∣v lies on path from root to rightmost leaf (excluding leaf)}
// 🔄 Final Order:
// Root→L→Leaves→R
// reverse
// 🌳 Example
//         1
//        / \
//       2   3
//      / \   \
//     4   5   6
//        / \  /
//       7  8 9
// Boundary Traversal:
// 1 → 2 → 4 → 7 → 8 → 9 → 6 → 3
// ⚙️ 2. Algorithm Idea
// Step-by-step:
// Add root
// Traverse left boundary
// Traverse all leaf nodes (in-order style)
// Traverse right boundary (store and reverse)





// 🧠 3. Complexity Analysis
#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
// Check if node is leaf
bool isLeaf(Node* node){
    return node->left==NULL && node->right==NULL;
}
void leftBoundary(Node* root,vector<int>&res){
    Node* current=root->left;
    while(current!=NULL){
        if(!isLeaf(current)) res.push_back(current->val);
        if(current->left!=NULL) current=current->left;
        else current=current->right;
    }
}
void rightBoundary(Node* root,vector<int>&res){
    Node* current=root->right;
    vector<int>temp;
    while(current!=NULL){
        if(!isLeaf(current)) temp.push_back(current->val);
        if(current->right!=NULL) current =current->right;
        else current=current->left;
    }
    // Reverse the right boundary and add to result
    for(int i=temp.size()-1; i>=0; i--){
        res.push_back(temp[i]);
    }
}
void leafNodes(Node* root,vector<int>&res){
    if(root==NULL) return;
    if(isLeaf(root)){
        res.push_back(root->val);
        return;
    }
    leafNodes(root->left,res);
    leafNodes(root->right,res);
}
vector<int>BoundaryTraversal(Node* root){
    if(root==NULL) return {};
    vector<int>res;
    if(!isLeaf(root))  res.push_back(root->val); // Add root if it's not a leaf
    leftBoundary(root,res);
    leafNodes(root,res);
    rightBoundary(root,res);
    return res;
}
int main(){
    Node* root=new Node(1);
    root->left=new Node(2);
    root->right= new Node(3);
    root->left->left= new Node(4);
    root->left->right= new Node(5);
    root->right->right= new Node(6);
    root->left->right->left= new Node(7);
    root->left->right->right= new Node(8);
    root->right->right->left= new Node(9);
    vector<int>boundary=BoundaryTraversal(root);
    cout<<"Boundary Traversal: ";
    for(int val: boundary){
        cout<<val<<" ";// Output: 1 2 4 7 8 9 6 3
    }
    cout<<endl;
    return 0;
}





// 🔧 2. INSERT in BST
// 🧠 Mathematical Idea
// Insertion is equivalent to finding the correct position in an ordered set.
// We recursively apply:
// x<v⇒goleft,x>v⇒goright






#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
Node* Insert(Node* root,int key){
    if(root==NULL) return new Node(key);
    if(key<root->val){
        root->left=Insert(root->left,key);
    }
    else if(key>root->val){
        root->right=Insert(root->right,key);
    }
    return root;
}
//insert 5,3,7,2,4,6,8 into BST and print inorder traversal (should be sorted)

int main(){
    Node* root=NULL;
    root=Insert(root,5);
    Insert(root,3);
    Insert(root,7);
    Insert(root,2);
    Insert(root,4);
    Insert(root,6);
    Insert(root,8);
    cout<<"BST Inorder Traversal: ";
    // Inorder traversal of BST gives sorted order
    function<void(Node*)> inorder=[&](Node* node){
        if(node==NULL) return;
        inorder(node->left);
        cout<<node->val<<" ";
        inorder(node->right);
    };
    inorder(root);
    cout<<endl;

    // The BST structure is now:
    //         5
    //        / \
    //       3   7
    //      / \ / \
    //     2  4 6  8
    return 0;
}




// 🔍 3. SEARCH in BST
// 🧠 Mathematical Idea
// BST gives us a divide-and-conquer search:
// T(n)=T(n/2)(on average)
// Base case:
// Search(NULL,key)=false
// Search(leaf,key)=true if leaf->val==key else false




#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val = data;
        left=NULL;
        right=NULL;
    }
};
bool Search(Node* root,int key){
    if(root==NULL) return false;
    if(root->val==key) return true;
    if(key<root->val){
        return Search(root->left,key);
    }
    else{
        return Search(root->right,key);
    }
}
int main(){
    Node* root = new Node(5);
    root->left= new Node(3);
    root->right= new Node(7);
    root->left->left= new Node(2);
    root->left->right= new Node(4);
    root->right->left= new Node(6);
    root->right->right= new Node(8);
    cout<<Search(root,4)<<endl;//output=1 (true)
    cout<<Search(root,10)<<endl;//output=0 (false)
    return 0;
}






// ❌ 4. DELETE in BST
// 🧠 Mathematical Cases
// Deletion in a BST can be categorized into three cases based on the degree of the node to be deleted:
// Case 1: Leaf Node (deg(v) = 0)
// If the node to be deleted is a leaf node, we can simply remove it from the tree without any further adjustments.
// Case 2: Node with One Child (deg(v) = 1)
// If the node to be deleted has only one child, we can replace the node with its child. This involves updating the parent of the node to point to the child instead of the node being deleted.
// Case 3: Node with Two Children (deg(v) = 2)
// If the node to be deleted has two children, we need to find a replacement for the node to maintain the properties of the BST. The common approach is to replace the node with either its inorder predecessor (the largest node in its left subtree) or its inorder successor (the smallest node in its right subtree). After replacing the node's value with that of the predecessor or successor, we then need to delete the predecessor or successor node, which will fall into either Case 1 or Case 2.
// Deleting node 
// Case 1: Leaf

// deg(v)=0⇒deletedirectly
// Case 2: One child
// deg(v)=1⇒replacevwithchild
// Case 3: Two children


// Replace with:
// Inorder predecessor (largest in left subtree)
// v=max(Left Subtree)
// or
// Inorder successor (smallest in right subtree)
// v=min(Right Subtree)






#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
Node* FindMin(Node* root){
    while(root->left!=NULL){
        root=root->left;
    }
    return root;
}
Node* Delete(Node* root,int key){
    if(root==NULL) return NULL;
    if(key<root->val){
        root->left=Delete(root->left,key);
    }
    else if(key>root->val){
        root->right=Delete(root->right,key);
    }
    else{
        // Node to be deleted found
        // Case 1: Leaf node
        if(root->left==NULL && root->right==NULL){
            delete root;
            return NULL;
        }
        // Case 2: One child
        else if(root->left==NULL){
            Node* temp=root->right;
            delete root;
            return temp;
        }
        else if(root->right==NULL){
            Node* temp=root->left;
            delete root;
            return temp;
        }
        // Case 3: Two children
        else{
            Node* temp=FindMin(root->right); // Find inorder successor
            root->val=temp->val; // Replace value
            root->right=Delete(root->right,temp->val); // Delete successor
        }

    }
    return root;

}
int main(){
    Node* root = new Node(5);
    root->left= new Node(3);
    root->right= new Node(7);
    root->left->left= new Node(2);
    root->left->right= new Node(4);
    root->right->left= new Node(6);
    root->right->right= new Node(8);
    // Delete node with value 3 (which has two children)
    root=Delete(root,3);
    cout<<"BST Inorder Traversal after deletion: ";
    // Inorder traversal of BST gives sorted order
    function<void(Node*)> inorder=[&](Node* node){
        if(node==NULL) return;
        inorder(node->left);
        cout<<node->val<<" ";
        inorder(node->right);
    };
    inorder(root);
    cout<<endl;
    // The BST structure after deletion of node 3 will be:
    //         5
    //        / \
    //       4   7
    //      /   / \
    //     2   6   8
    return 0;
}





// ✅ 5. VALID BST
// 🧠 Mathematical Definition

// A tree is valid if: ∀v:low<v<high
// We propagate constraints:
// Left subtree → (low,v)
// Right subtree → (v,high)




#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
bool IsValidBST(Node* root,long long low=LLONG_MIN,long long high=LLONG_MAX){
    if(root==NULL) return true;
    if(root->val<=low || root->val>=high) return false;
    return IsValidBST(root->left,low,root->val) && IsValidBST(root->right,root->val,high);
}
int main(){
    Node* root = new Node(5);
    root->left= new Node(3);
    root->right= new Node(7);
    root->left->left= new Node(2);
    root->left->right= new Node(4);
    root->right->left= new Node(6);
    root->right->right= new Node(8);
    cout<<IsValidBST(root)<<endl;//output=1 (true)
    // Modify tree to make it invalid
    root->right->left->val=10; // Change value of node 6 to 10
    cout<<IsValidBST(root)<<endl;//output=0 (false)
    return 0;
}



// 🔢 6. Kth Smallest / Largest
// 🧠 Mathematical Insight

// BST inorder traversal = sorted order

// Inorder
// =
// sorted sequence
// Inorder=sorted sequence



//case 1. Kth Smallest
// KthSmallest(root,k):
// Perform inorder traversal and return k-1 indexed element
//case 2. Kth Largest
// KthLargest(root,k):
// Perform reverse inorder traversal and return k-1 indexed element
// Reverse Inorder = sorted sequence in reverse order
// Reverse Inorder=sorted sequence in reverse order
// 🔍 Step-by-Step Validation
// Inorder Traversal: 2 → 3 → 4 → 5 → 6 → 7 → 8
// K=3
// Kth Smallest: 4 (3rd element in sorted order)
// Kth Largest: 6 (3rd element from end in sorted order)
// ✔ Output: Kth Smallest = 4, Kth Largest = 6
// 🔹 C++ Example: Kth Smallest and Largest in BST



#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
void Inorder(Node* root,vector<int>&res){
    if(root==NULL) return;
    Inorder(root->left,res);
    res.push_back(root->val);
    Inorder(root->right,res);
}
int KthSmallest(Node* root,int k){
    vector<int>inorder;
    Inorder(root,inorder);
    if(k-1<inorder.size()) return inorder[k-1];
    return -1; // k is out of bounds
}
int KthLargest(Node* root,int k){
    vector<int>inorder;
    Inorder(root,inorder);
    if(k-1<inorder.size()) return inorder[inorder.size()-k];
    return -1; // k is out of bounds
}
int main(){
    Node* root = new Node(5);
    root->left= new Node(3);
    root->right= new Node(7);
    root->left->left= new Node(2);
    root->left->right= new Node(4);
    root->right->left= new Node(6);
    root->right->right= new Node(8);
    int k=3;
    cout<<"Kth Smallest: "<<KthSmallest(root,k)<<endl;//output=4
    cout<<"Kth Largest: "<<KthLargest(root,k)<<endl;//output=6
    return 0;
}






// 🌳 1. Problem Understanding
// We want to:
// Serialize → Convert a tree into a string
// Deserialize → Reconstruct the same tree from that string

// 👉 Mathematically:

// We want a bijection (1–1 mapping):
// f:Tree↔String
// Such that:
//f inverse(f(T))=T


// 🧠 2. Mathematical Insight
// A binary tree is defined recursively:
// T=(v,Tleft,Tright)

// So we encode it recursively.

// 🔑 Key Idea: Include NULL nodes

// Without nulls, structure is lost.

// Example:

// Tree 1:       Tree 2:
//    1             1
//   /               \
//  2                 2

// Both give: 1 2 ❌ (ambiguous)

// 👉 So we must encode: NULL=#
// 🔄 3. Serialization Strategy

// We use Preorder Traversal:
// Root → Left → Right

// 📌 Mathematical Form:
// f(t)=v,f(Tleft),f(Tright) and f(NULL)=#


// 🔁 4. Deserialization Strategy

// We reverse the process:
//T=v,f inverse(L) w,f inverse(R) and f inverse(#)=NULL

// if token = #
// otherwise
// 	​

// 🌟 Example

// Tree:

//         1
//        / \
//       2   3
//          / \
//         4   5
// Serialized:
// 1 2 # # 3 4 # # 5 # #


// #include<bits/stdc++.h>
// using namespace std;
// struct Node{
//     int val;
//     Node* left;
//     Node* right;
//     Node(int data){
//         val=data;
//         left=NULL;
//         right=NULL;
//     }
// };
// string SerializeTree(Node* root){
//     if(root==NULL) return "#";
//     return to_string(root->val)+" "+SerializeTree(root->left)+" "+SerializeTree(root->right);
// }
// Node* DeserializeTree(istringstream& iss){
//     string token;
//     if(!(iss>>token)) return NULL; // No more tokens
//     if(token=="#") return NULL; // Null node
//     Node* node=new Node(stoi(token)); // Create node with value
//     node->left=DeserializeTree(iss); // Deserialize left subtree
//     node->right=DeserializeTree(iss); // Deserialize right subtree
//     return node;
// }
// int main(){
//     Node* root=new Node(1);
//     root->left=new Node(2);
//     root->right=new Node(3);
//     root->right->left=new Node(4);
//     root->right->right=new Node(5);
//     string serialized=SerializeTree(root);
//     cout<<"Serialized Tree: "<<serialized<<endl;//output=1 2 # # 3 4 # # 5 # #
//     istringstream iss(serialized);
//     Node* deserializedRoot=DeserializeTree(iss);
//     cout<<"Deserialization successful: "<<(deserializedRoot!=NULL)<<endl;//output=1 (true)
//     return 0;
// }






// ⭐⭐⭐ 7. Binary Lifting
// 🧠 Mathematical Idea

// We want to answer:
// ancestor(v,k)

// Instead of moving k steps one-by-one, we decompose:
// k=∑2^i

// 👉 Like binary representation: b0, b1, b2, ...
//k=b0+b1*2+b2*4+...+bi*2^i+...
// So we precompute:
// up[v][i]=2^i-th ancestor of v
// ⚙️ Preprocessing
// up[v][i]=up[up[v][i−1]][i−1]





#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
const int N=100005; // Maximum number of nodes
const int MAX_LOG=20; // Assuming tree height won't exceed 2^20
vector<int>adj[N]; // Adjacency list for tree
int up[N][MAX_LOG]; // up[v][i] = 2^i-th ancestor of v
int depth[N]; // depth[v] = depth of node v
void dfs(int v,int p){
    up[v][0]=p;// 2^0-th ancestor is parent
    for(int i=1;i<MAX_LOG;i++){
        if(up[v][i-1]!=-1){
           up[v][i]=up[up[v][i-1]][i-1];// Precompute 2^i-th ancestor
        }
         else{
            up[v][i]=-1;// No ancestor at this level
         }  
    }
    for(int u: adj[v]){
        if(u!=p){
            depth[u]=depth[v]+1;// Set depth of child
            dfs(u,v);// Recur for child
        }
    }
}
int ancestor(int v,int k){
    for(int i=0;i<MAX_LOG;i++){
        if(k&(1<<i)){// if the i-th bit of k is set
            v=up[v][i];// Move up to 2^i-th ancestor
            if(v==-1) return -1;// No ancestor at this level
        }
    }
    return v;
}
int main(){
    memset(up, -1, sizeof(up));
    //Example tree construction
    //         0
    //        / \
    //       1   2
    //      / \
    //     3   4
    // Add edges to adjacency list
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[1].push_back(3);
    adj[1].push_back(4);
    adj[2].push_back(0);
    adj[3].push_back(1);
    adj[4].push_back(1);
    // Preprocess for binary lifting
    depth[0]=0;// Root node depth
    dfs(0,-1);// Start DFS from root with no parent
    // Example queries
    cout<<"Ancestor of 3 at distance 1: "<<ancestor(3,1)<<endl;//output=1
    cout<<"Ancestor of 3 at distance 2: "<<ancestor(3,2)<<endl;//output=0
    cout<<"Ancestor of 3 at distance 4: "<<ancestor(3,4)<<endl;//output=-1 (no ancestor)
    cout<<"Ancestor of 3 at distance 3: "<<ancestor(3,3)<<endl;//output=-1 (no ancestor)
    return 0;  
}








// 🌿 LCA using Binary Lifting
// 🧠 Idea:
// Bring nodes to same depth, then lift together.
// Steps:
// 1. If depth[u]<depth[v], swap(u,v)
// 2. Lift u up to depth of v
// 3. If u==v, return u
// 4. Lift u and v together until their ancestors differ
// 5. Return parent of u (or v)



#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
const int N=100005; // Maximum number of nodes
const int MAX_LOG=20; // Assuming tree height won't exceed 2^20
vector<int>adj[N]; // Adjacency list for tree
int up[N][MAX_LOG]; // up[v][i] = 2^i-th ancestor of v
int depth[N]; // depth[v] = depth of node v
void dfs(int v,int p){
    up[v][0]=p;// 2^0-th ancestor is parent
    for(int i=1;i<MAX_LOG;i++){
        if(up[v][i-1]!=-1){
           up[v][i]=up[up[v][i-1]][i-1];// Precompute 2^i-th ancestor
        }
         else{
            up[v][i]=-1;// No ancestor at this level
         }  
    }
    for(int u: adj[v]){
        if(u!=p){
            depth[u]=depth[v]+1;// Set depth of child
            dfs(u,v);// Recur for child
        }
    }
}
int kthAncestor(int v,int k){
    for(int i=0;i<MAX_LOG;i++){
        if(k&(1<<i)){// if the i-th bit of k is set
            v=up[v][i];// Move up to 2^i-th ancestor
            if(v==-1) return -1;// No ancestor at this level
        }
    }
    return v;
}

int lca (int u,int v){
    if(depth[u]<depth[v]) swap(u,v);// Ensure u is deeper
    // Lift u up to depth of v
    int diff=depth[u]-depth[v];
    u=kthAncestor(u,diff);
    if(u==v) return u;// If v is ancestor of u
    // Lift u and v together until their ancestors differ
    for(int i=MAX_LOG-1;i>=0;i--){
        if(up[u][i]!=up[v][i]){// If ancestors differ at this level
            u=up[u][i];// Move u up
            v=up[v][i];// Move v up

        }
    }
    return up[u][0];// Return parent of u (or v) as LCA
}
int main(){
    memset(up, -1, sizeof(up));
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[1].push_back(3);
    adj[1].push_back(4);
    adj[2].push_back(0);
    adj[3].push_back(1);
    adj[4].push_back(1);
    // Preprocess for binary lifting
    depth[0]=0;// Root node depth
    dfs(0,-1);// Start DFS from root with no parent
    // Example LCA queries
    cout<<"LCA of 3 and 4: "<<lca(3,4)<<endl;//output=1
    cout<<"LCA of 3 and 2: "<<lca(3,2)<<endl;//output=0
    cout<<"LCA of 4 and 2: "<<lca(4,2)<<endl;//output=0
    return 0;  
}


// ⏱ Complexity
// Preprocessing: O(NlogN)
// Query: O(logN)





// ⭐⭐⭐ 8. Euler Tour Technique
// 🧠 Mathematical View
// Flatten tree → array
// We assign entry time (tin) and exit time (tout)
// Subtree(v)=[tin[v],tout[v]]
// Ancestor check: u is ancestor of v if tin[u]<tin[v] && tout[u]>tout[v]
// LCA: Binary search on Euler tour array
// Euler Tour: DFS traversal that records entry and exit times of nodes
// For each node v:
// tin[v] = time when we first visit v
// tout[v] = time when we finish processing v
// Subtree of v corresponds to the interval [tin[v], tout[v]]
// Ancestor check: u is ancestor of v if tin[u] < tin[v] &&
// tout[u] > tout[v]
// LCA: Binary search on Euler tour array to find the lowest common ancestor
// Example:
//         0
//        / \
//       1   2
//      / \
//     3   4
// Euler Tour: 0 (tin=0) → 1 (tin=1)
// → 3 (tin=2) → 3 (tout=3) → 1 (tout=4) → 4 (tin=5) → 4 (tout=6) → 0 (tout=7)
// Subtree(1)=[1,4]
// Ancestor check: Is 0 ancestor of 3? tin[0]<tin[3] && tout[0]>tout[3] → true
// LCA(3,4): Binary search on Euler tour array to find lowest common ancestor
// Implementation of Euler Tour Technique for LCA



#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
const int N=100005; // Maximum number of nodes
vector<int>adj[N]; // Adjacency list for tree
int tin[N], tour[N],timer=0;// tin[v] = entry time of node v, tour[timer] = node at time timer

int value[N]; // value[v] = value of node v
//segment tree for range minimum query (RMQ) on Euler tour
int segtree[4*N]; // Segment tree array
void dfs(int v,int p){
    tin[v]=timer;// set entry time
    tour[timer]=v;// record node in Euler tour
    timer++;
    for(int u: adj[v]){
        if(u!=p){
            dfs(u,v);// Recur for child
            tour[timer]=v;// record node again after visiting child
            timer++;
        }
    }
}
void build(int idx,int left,int right){
    if(left==right){
        int treeNode=tour[left];
        segtree[idx] = tour[left]; // Store node index in segment tree
        return;
    }
    int mid=(left+right)/2;
    build(2*idx,left,mid);
    build(2*idx+1,mid+1,right);
    // Store the node with minimum value in the segment tree
    //segtree[idx]=(value[segtree[2*idx]]<value[segtree[2*idx+1]])?segtree[2*idx]:segtree[2*idx+1];
    segtree[idx]=segtree[2*idx] + segtree[2*idx+1]; // For LCA, we store the node index directly
}
int query(int idx,int left,int right,int ql,int qr){
    if(qr<left || ql>right) return -1; // No overlap
    if(ql<=left && right<=qr) return segtree[idx]; // Total overlap
    int mid=(left+right)/2;
    int leftAns=query(2*idx,left,mid,ql,qr);
    int rightAns=query(2*idx+1,mid+1,right,ql,qr);
    if(leftAns==-1) return rightAns;
    if(rightAns==-1) return leftAns;
    // Return the node with minimum value
    //return (value[leftAns]<value[rightAns])?leftAns:rightAns;
    return leftAns + rightAns; // For LCA, we return the node index directly
}
int lca(int u,int v){
    if(tin[u]>tin[v]) swap(u,v);// Ensure u is earlier in Euler tour
    return query(1,0,timer-1,tin[u],tin[v]);// Query segment tree for LCA
}
void update(int idx,int left,int right,int pos,int newVal){
    if(left==right){
        segtree[idx]=pos; // Update node index in segment tree
        return;
    }
    int mid=(left+right)/2;
    if(pos<=mid) update(2*idx,left,mid,pos,newVal);
    else update(2*idx+1,mid+1,right,pos,newVal);
    // Update the segment tree after modification
    //segtree[idx]=(value[segtree[2*idx]]<value[segtree[2*idx+1]])?segtree[2*idx]:segtree[2*idx+1];
    segtree[idx]=segtree[2*idx] + segtree[2*idx+1]; // For LCA, we store the node index directly
}
int main(){
    // Example tree construction
    //         0
    //        / \
    //       1   2
    //      / \
    //     3   4
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[1].push_back(3);
    adj[1].push_back(4);
    adj[2].push_back(0);
    adj[3].push_back(1);
    adj[4].push_back(1);
       // Node values
    value[0] = 5;
    value[1] = 3;
    value[2] = 6;
    value[3] = 2;
    value[4] = 1;
    // Preprocess for Euler tour
    dfs(0,-1);// Start DFS from root with no parent
    build(1,0,timer-1);// Build segment tree on Euler tour

  // Subtree sum of node 1
    int l = tin[1];
    int r = tour[1];

    cout << "Subtree sum of node 1: "
         << query(1, 0, timer-1, l, r) << endl;

    // Update node 3 value to 10
    update(1, 0, timer-1, tin[3], 10);

    cout << "After update, subtree sum of node 1: "
         << query(1, 0, timer-1, l, r) << endl;


    // Example LCA queries
    cout<<"LCA of 3 and 4: "<<lca(3,4)<<endl;//output=1
    cout<<"LCA of 3 and 2: "<<lca(3,2)<<endl;//output=0
    cout<<"LCA of 4 and 2: "<<lca(4,2)<<endl;//output=0
    return 0;  
}




//2.method implimentation of Euler Tour Technique for LCA and subtree queries with segment tree for sum queries
// ⚠️ Important clarification first:

// 👉 Classic LCA (Euler + RMQ) does NOT support updates efficiently
// Because:

// Euler Tour + RMQ is static (immutable)
// Euler Tour + RMQ is static (immutable)

// So if you want updates, you must define what you are updating:

// ✅ What we WILL build (Correct & Useful)

// We’ll combine:

// 🔹 1. LCA → using Binary Lifting (supports tree queries)
// 🔹 2. Subtree Updates + Queries → using Euler Tour + Segment Tree
// 🧠 Mathematical Model
// Tree → Array Mapping:
// subtree(v)=[tin[v],tout[v]]
// Segment Tree:
// Range Sum / Update on subtree
// LCA:
// O(logN) using Binary Lifting








#include<bits/stdc++.h>
using namespace std;

const int N = 100005;
const int LOG = 20;

vector<int> adj[N];

// -------- Binary Lifting --------
int up[N][LOG];
int depth[N];

// -------- Euler Tour --------
int tin[N], tout[N], flat[N];
int timer = 0;

// -------- Values --------
int value[N];

// -------- Segment Tree --------
int seg[4*N];

// ---------------- DFS ----------------
void dfs(int v, int p) {

    // Binary lifting
    up[v][0] = p;
    for(int i = 1; i < LOG; i++) {
        if(up[v][i-1] != -1)
            up[v][i] = up[up[v][i-1]][i-1];
        else
            up[v][i] = -1;
    }

    // Euler Tour
    tin[v] = timer;
    flat[timer] = v;
    timer++;

    for(int u : adj[v]) {
        if(u != p) {
            depth[u] = depth[v] + 1;
            dfs(u, v);
        }
    }

    tout[v] = timer - 1;
}

// ---------------- BUILD ----------------
void build(int node, int start, int end) {
    if(start == end) {
        int v = flat[start];
        seg[node] = value[v];
        return;
    }

    int mid = (start + end) / 2;

    build(2*node, start, mid);
    build(2*node+1, mid+1, end);

    seg[node] = seg[2*node] + seg[2*node+1];
}

// ---------------- QUERY ----------------
int query(int node, int start, int end, int l, int r) {
    if(r < start || end < l) return 0;

    if(l <= start && end <= r)
        return seg[node];

    int mid = (start + end) / 2;

    return query(2*node, start, mid, l, r) +
           query(2*node+1, mid+1, end, l, r);
}

// ---------------- UPDATE ----------------
void update(int node, int start, int end, int idx, int val) {
    if(start == end) {
        seg[node] = val;
        return;
    }

    int mid = (start + end) / 2;

    if(idx <= mid)
        update(2*node, start, mid, idx, val);
    else
        update(2*node+1, mid+1, end, idx, val);

    seg[node] = seg[2*node] + seg[2*node+1];
}

// ---------------- Kth Ancestor ----------------
int kthAncestor(int v, int k) {
    for(int i = 0; i < LOG; i++) {
        if(k & (1 << i)) {
            if(v == -1) return -1;
            v = up[v][i];
        }
    }
    return v;
}

// ---------------- LCA ----------------
int lca(int a, int b) {

    if(depth[a] < depth[b]) swap(a, b);

    int diff = depth[a] - depth[b];
    a = kthAncestor(a, diff);

    if(a == b) return a;

    for(int i = LOG-1; i >= 0; i--) {
        if(up[a][i] != -1 && up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }

    return up[a][0];
}

// ---------------- MAIN ----------------
int main() {

    memset(up, -1, sizeof(up));

    // Tree:
    //         0
    //        / \
    //       1   2
    //      / \
    //     3   4

    adj[0].push_back(1);
    adj[0].push_back(2);

    adj[1].push_back(0);
    adj[1].push_back(3);
    adj[1].push_back(4);

    adj[2].push_back(0);
    adj[3].push_back(1);
    adj[4].push_back(1);

    // Values
    value[0] = 5;
    value[1] = 3;
    value[2] = 6;
    value[3] = 2;
    value[4] = 1;

    // Preprocessing
    depth[0] = 0;
    dfs(0, -1);

    build(1, 0, timer-1);

    // -------- Subtree Query --------
    int v = 1;
    cout << "Subtree sum of node 1: "
         << query(1, 0, timer-1, tin[v], tout[v]) << endl;//output=6 (3 + 2 + 1)

    // -------- Update --------
    cout << "Updating node 3 to value 10\n";
    update(1, 0, timer-1, tin[3], 10);// Update value of node 3 in segment tree

    cout << "After update, subtree sum of node 1: "
         << query(1, 0, timer-1, tin[v], tout[v]) << endl;//output=14 (3 + 10 + 1)

    cout << endl;

    // -------- LCA --------
    cout << "LCA of 3 and 4: " << lca(3,4) << endl;//output=1
    cout << "LCA of 3 and 2: " << lca(3,2) << endl;//output=0
    cout << "LCA of 4 and 2: " << lca(4,2) << endl;//output=0

    return 0;
}








// ⭐⭐⭐ 10. Heavy Light Decomposition (HLD)
// 🧠 Mathematical Idea
// Break tree into chains to reduce path query:
// Tree Path = O(N) edges
//  segments
// Tree Path⇒O(logN) segments

// 🧠 Mathematical Idea of HLD
// We want to answer:
// Query on path (u→v)

// A path in a tree can be long  O(N), so we break it into:
// O(log N) disjoint segments

// 🔑 Core Concept

// For every node:

// Choose one heavy child:
// heavy child=argmax(subtree size)
// Other edges → light edges
// 🔥 Key Property
// Number of light edges from root to any node≤logN

// 👉 So path can be split into log N chains
// ⚙️ Steps of HLD
// 🔹 Step 1: DFS → Compute
// parent[v]
// depth[v]
// subtree size
// heavy[v]
// 🔹 Step 2: Decompose Tree

// Assign:

// head[v] → chain head
// pos[v] → position in base array
// 🔹 Step 3: Segment Tree

// Build on baseArray[pos[v]]





#include<bits/stdc++.h>
using namespace std;

const int N = 100005;

vector<int> adj[N];

// -------- HLD Arrays --------
int parent[N], depth[N], heavy[N], head[N], pos[N];
int subtree[N];
int cur_pos = 0;

// -------- Values --------
int value[N];
int baseArray[N];

// -------- Segment Tree --------
int seg[4*N];

// ---------------- DFS (Find Heavy Child) ----------------
int dfsHLD(int v, int p) {
    parent[v] = p;
    subtree[v] = 1;
    int max_size = 0;

    for(int u : adj[v]) {
        if(u != p) {
            depth[u] = depth[v] + 1;
            int size = dfsHLD(u, v);
            subtree[v] += size;

            if(size > max_size) {
                max_size = size;
                heavy[v] = u;
            }
        }
    }
    return subtree[v];
}

// ---------------- Decompose ----------------
void decompose(int v, int h) {
    head[v] = h;
    pos[v] = cur_pos;

    baseArray[cur_pos] = value[v];
    cur_pos++;

    if(heavy[v] != -1)
        decompose(heavy[v], h);

    for(int u : adj[v]) {
        if(u != parent[v] && u != heavy[v]) {
            decompose(u, u);
        }
    }
}

// ---------------- Segment Tree Build ----------------
void build(int node, int start, int end) {
    if(start == end) {
        seg[node] = baseArray[start];
        return;
    }

    int mid = (start + end) / 2;

    build(2*node, start, mid);
    build(2*node+1, mid+1, end);

    seg[node] = seg[2*node] + seg[2*node+1];
}

// ---------------- Query ----------------
int query(int node, int start, int end, int l, int r) {
    if(r < start || end < l) return 0;

    if(l <= start && end <= r)
        return seg[node];

    int mid = (start + end) / 2;

    return query(2*node, start, mid, l, r) +
           query(2*node+1, mid+1, end, l, r);
}

// ---------------- Update ----------------
void update(int node, int start, int end, int idx, int val) {
    if(start == end) {
        seg[node] = val;
        return;
    }

    int mid = (start + end) / 2;

    if(idx <= mid)
        update(2*node, start, mid, idx, val);
    else
        update(2*node+1, mid+1, end, idx, val);

    seg[node] = seg[2*node] + seg[2*node+1];
}

// ---------------- HLD Query (Path u → v) ----------------
int queryPath(int a, int b) {
    int res = 0;

    while(head[a] != head[b]) {
        if(depth[head[a]] < depth[head[b]])
            swap(a, b);

        int headA = head[a];

        res += query(1, 0, cur_pos-1, pos[headA], pos[a]);

        a = parent[headA];
    }

    // Same chain
    if(depth[a] > depth[b]) swap(a, b);

    res += query(1, 0, cur_pos-1, pos[a], pos[b]);

    return res;
}

// ---------------- MAIN ----------------
int main() {

    memset(heavy, -1, sizeof(heavy));

    // Tree:
    //         0
    //        / \
    //       1   2
    //      / \
    //     3   4

    adj[0].push_back(1);
    adj[0].push_back(2);

    adj[1].push_back(0);
    adj[1].push_back(3);
    adj[1].push_back(4);

    adj[2].push_back(0);
    adj[3].push_back(1);
    adj[4].push_back(1);

    // Values
    value[0] = 5;
    value[1] = 3;
    value[2] = 6;
    value[3] = 2;
    value[4] = 1;

    // Step 1: DFS
    depth[0] = 0;
    dfsHLD(0, -1);

    // Step 2: Decompose
    decompose(0, 0);

    // Step 3: Segment Tree
    build(1, 0, cur_pos-1);

    // -------- Queries --------
    cout << "Path sum (3 → 4): " << queryPath(3,4) << endl;
    cout << "Path sum (3 → 2): " << queryPath(3,2) << endl;

    // -------- Update --------
    cout << "Update node 3 to value 10\n";
    update(1, 0, cur_pos-1, pos[3], 10);

    cout << "Path sum (3 → 4): " << queryPath(3,4) << endl;

    return 0;
}





// ⭐⭐⭐ 14. Advanced Traversal Techniques

// We’ll cover:

// 🧠 Morris Traversal (O(1) space)
// 🔁 Iterative Traversals (Stack-based)
// 💻 Full C++ implementations
// 🎯 Mathematical intuition
// 🧠 1. Morris Traversal (O(1) Space)
// 🔑 Core Idea (Mathematical View)

// A binary tree has:
// Edges=N−1

// 👉 Morris uses unused NULL pointers to create temporary links:
// Tree⇒Threaded Binary Tree
// 🔄 Concept

// For each node:

// If left is NULL → visit node
// Else:
// Find inorder predecessor
// Create temporary link:
// predecessor.right=current
// 🎯 Why it works?

// We simulate recursion stack using:

// temporary back edges
// temporary back edges
// 🌳 Visualization

// Think:

// Left subtree → predecessor → back to root




// ⭐ Morris Traversal (O(1) space)
// ⭐ Iterative Traversals (stack-based)
// 🔁 2. Iterative Traversals
// 🧠 Why Iterative?

// Recursion uses: O(H) space (call stack)
// We simulate it using explicit stack
// 🔹 Iterative Inorder
// Idea:
// Go Left → Visit → Go Right
// Iterative Preorder
// Idea:
// Root → Left → Right





#include<bits/stdc++.h>
using namespace std;

// -------- Node Definition --------
struct Node {
    int val;
    Node* left;
    Node* right;

    Node(int x) {
        val = x;
        left = right = NULL;
    }
};

// ======================================================
// 🔁 ITERATIVE TRAVERSALS
// ======================================================

// -------- Inorder (Iterative) --------
void inorderIterative(Node* root) {
    stack<Node*> st;
    Node* curr = root;

    while(curr || !st.empty()) {
        while(curr) {
            st.push(curr);
            curr = curr->left;
        }

        curr = st.top();
        st.pop();

        cout << curr->val << " ";

        curr = curr->right;
    }
}

// -------- Preorder (Iterative) --------
void preorderIterative(Node* root) {
    if(!root) return;

    stack<Node*> st;
    st.push(root);

    while(!st.empty()) {
        Node* curr = st.top();
        st.pop();

        cout << curr->val << " ";

        if(curr->right) st.push(curr->right);
        if(curr->left) st.push(curr->left);
    }
}

// -------- Postorder (2 Stacks) --------
void postorderIterative(Node* root) {
    if(!root) return;

    stack<Node*> st1, st2;
    st1.push(root);

    while(!st1.empty()) {
        Node* curr = st1.top();
        st1.pop();
        st2.push(curr);

        if(curr->left) st1.push(curr->left);
        if(curr->right) st1.push(curr->right);
    }

    while(!st2.empty()) {
        cout << st2.top()->val << " ";
        st2.pop();
    }
}

// ======================================================
// 🧠 MORRIS TRAVERSALS (O(1) SPACE)
// ======================================================

// -------- Morris Inorder --------
void morrisInorder(Node* root) {
    Node* curr = root;

    while(curr) {

        if(curr->left == NULL) {
            cout << curr->val << " ";
            curr = curr->right;
        }
        else {
            Node* pred = curr->left;

            while(pred->right && pred->right != curr)
                pred = pred->right;

            if(pred->right == NULL) {
                pred->right = curr;   // create thread
                curr = curr->left;
            }
            else {
                pred->right = NULL;   // remove thread
                cout << curr->val << " ";
                curr = curr->right;
            }
        }
    }
}

// -------- Morris Preorder --------
void morrisPreorder(Node* root) {
    Node* curr = root;

    while(curr) {

        if(curr->left == NULL) {
            cout << curr->val << " ";
            curr = curr->right;
        }
        else {
            Node* pred = curr->left;

            while(pred->right && pred->right != curr)
                pred = pred->right;

            if(pred->right == NULL) {
                cout << curr->val << " "; // visit before going left
                pred->right = curr;
                curr = curr->left;
            }
            else {
                pred->right = NULL;
                curr = curr->right;
            }
        }
    }
}

// ======================================================
// 🌳 MAIN FUNCTION
// ======================================================

int main() {

    // Tree:
    //         1
    //        / \
    //       2   3
    //      / \
    //     4   5

    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "Iterative Inorder: ";
    inorderIterative(root);
    cout << endl;

    cout << "Iterative Preorder: ";
    preorderIterative(root);
    cout << endl;

    cout << "Iterative Postorder: ";
    postorderIterative(root);
    cout << endl;

    cout << endl;

    cout << "Morris Inorder: ";
    morrisInorder(root);
    cout << endl;

    cout << "Morris Preorder: ";
    morrisPreorder(root);
    cout << endl;

    return 0;
}