medium-level-tree.cpp

// 🔹 1. Height of Tree
// 🧠 Mathematical Definition
// Height(T)=max(Height(left),Height(right))+1

// Base case:
// Height(NULL)=−1 (edge-based)or0 (node-based)
// 🔹 2. Level
// 🧠 Mathematical Definition
// Level(T)=max(Level(left),Level(right))+1
// Base case:
// Level(NULL)=0
// 🔹 3. Diameter of Tree
// 🧠 Mathematical Definition
// Diameter(T)=max(Diameter(left),Diameter(right),Height(left)+Height(right)+2)
// Base case:
// Diameter(NULL)=0
// 🔹 4. Maximum Path Sum in Binary Tree
// 🧠 Mathematical Definition
// MaxPathSum(T)=max(MaxPathSum(left),MaxPathSum(right),max(0,MaxPathSumFromNode(left))+max(0,MaxPathSumFromNode(right))+T.val)
// Base case:
// MaxPathSum(NULL)=0
// 🔹 5. Check if Tree is Balanced
// 🧠 Mathematical Definition
// A tree is balanced if for every node, the difference in height between its left and right subtrees is at most 1.
// Base case:
// A tree is balanced if for every node, the difference in height between its left and right subtrees is at most 1.
// 🔹 6. Check if Tree is Symmetric
// 🧠 Mathematical Definition
// A tree is symmetric if the left subtree is a mirror reflection of the right subtree.
// Base case:
// A tree is symmetric if the left subtree is a mirror reflection of the right subtree.
// 🔹 7. Binary Search (Recursion)
// 🧠 Mathematical Definition
// Binary Search(low,high):
// mid=low+(high-low)/2
// if arr[mid]==target return mid
// if target<arr[mid] return Binary Search(low,mid-1)
// if target>arr[mid] return Binary Search(mid+1,high)
// Base case:
// if low>high return -1 (target not found in the array)
// if arr[mid]==target return mid (target found at index mid)
// 🔹 8. Count Nodes in Binary Tree
// 🧠 Mathematical Definition
// CountNodes(T)=CountNodes(left)+CountNodes(right)+1
// Base case:
// CountNodes(NULL)=0
// 🔹 9. Count Leaf Nodes in Binary Tree
// 🧠 Mathematical Definition
// CountLeafNodes(T)=CountLeafNodes(left)+CountLeafNodes(right)
// Base case:
// CountLeafNodes(NULL)=0
// CountLeafNodes(leaf)=1
// 🔹 10. Count Non-Leaf Nodes in Binary Tree
// 🧠 Mathematical Definition
// CountNonLeafNodes(T)=CountNonLeafNodes(left)+CountNonLeafNodes(right)+1
// Base case:
// CountNonLeafNodes(NULL)=0
// CountNonLeafNodes(leaf)=0
// 🔹 11. Count Nodes at K-th Level in Binary Tree
// 🧠 Mathematical Definition
// CountNodesAtK(T,k)=CountNodesAtK(left,k-1)+CountNodesAtK(right,k-1)
// Base case:
// CountNodesAtK(NULL,k)=0
// CountNodesAtK(node,k)=1 if k==0 else 0
// 🔹 12. Count Nodes in Complete Binary Tree
// 🧠 Mathematical Definition
// CountNodes(T)=2^h-1 where h is the height of the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔹 13. Count Nodes in Perfect Binary Tree
// 🧠 Mathematical Definition
// CountNodes(T)=2^(h+1)-1 where h is the height of the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔹 14. Count Nodes in Full Binary Tree
// 🧠 Mathematical Definition
// CountNodes(T)=2*h+1 where h is the height of the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔹 15. Count Nodes in Binary Tree with N Nodes
// 🧠 Mathematical Definition
// CountNodes(T)=N where N is the total number of nodes in the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔹 16. Count Nodes in Binary Tree with L Leaves
// 🧠 Mathematical Definition
// CountNodes(T)=2*L-1 where L is the total number of leaf nodes in the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔹 17. Count Nodes in Binary Tree with N Non-Leaf Nodes
// 🧠 Mathematical Definition
// CountNodes(T)=N where N is the total number of non-leaf nodes in the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=0
// 🔹 18. Count Nodes in Binary Tree with N Nodes at K-th Level
// 🧠 Mathematical Definition
// CountNodes(T,k)=N where N is the total number of nodes at k-th level in the tree
// Base case:
// CountNodes(NULL,k)=0
// CountNodes(node,k)=1 if k==0 else 0
// 🔹 19. Count Nodes in Binary Tree with N Nodes and L Leaves
// 🧠 Mathematical Definition
// CountNodes(T)=N where N is the total number of nodes in the tree and L is the total number of leaf nodes in the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔹 20. Count Nodes in Binary Tree with N Nodes and L Non-Leaf Nodes
// 🧠 Mathematical Definition
// CountNodes(T)=N where N is the total number of nodes in the tree and L is the total number of non-leaf nodes in the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=0


// 🌳 1. Deletion in Binary Tree (General Case)
// 🧠 Idea (Mathematical Thinking)
// To delete node with value  𝑥
// Find:
// Target node  𝑇
// Deepest node  𝐷
// Replace: T←D
// Base case:
// When we have found the target node and performed the necessary replacement and deletion, we return the modified tree; otherwise, we continue to search for the target node in the left and right subtrees.
// 🔹 C++ Example: Deletion in Binary Tree








// 🔹 1. Height of Tree
// 🧠 Mathematical Definition
// Height(T)=max(Height(left),Height(right))+1
// Base case:
// Height(NULL)=−1 (edge-based)or0 (node-based)


#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int height(Node* root){
    if(root==NULL) return -1;
    int leftheight=height(root->left);
    int rightheight=height(root->right);
    return max(leftheight,rightheight)+1;
}
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);
    cout<<height(root)<<endl;
    return 0;
}




// 🔹 2. Level
// 🧠 Mathematical Definition
// Level(T)=max(Level(left),Level(right))+1
// Base case:
// Level(NULL)=0



#include<bits/stdc++.h>
using namespace std;
struct Node{
int val;
Node* left;
Node* right;
Node(int data){
val=data;
left=NULL;
right=NULL;
}
};
int level(Node* root){
    if(root==NULL) return 0;
    int leftlevel=level(root->left);
    int rightlevel=level(root->right);
    return max(leftlevel,rightlevel)+1;
}
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);
    cout<<level(root)<<endl;// Output: 3
    return 0;
}




// 🔹 3. Diameter of Tree
// 🧠 Mathematical Definition
// Diameter(T)=max(Diameter(left),Diameter(right),Height(left)+Height(right)+2)
// Base case:
// Diameter(NULL)=0
// 🧠 Why +2?
// Because:
// Diameter through root=left height+right height+2
// 👉 Each edge contributes +1
// 🔁 Dry Run (Small Example)
//     1
//    / \
//   2   3
// leftheight = 0
// rightheight = 0
// Diameter
// Diameter=0+0+2=2
// ✔ Correct (edges: 2→1→3)





#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int Diameter(Node* root,int &height){
    if(root==NULL){
        height=-1;
        return 0;
    }
    int leftheight=0,rightheight=0;
    int leftdiameter=Diameter(root->left,leftheight);
    int rightdiameter=Diameter(root->right,rightheight);
    height=max(leftheight,rightheight)+1;
    return max({leftdiameter,rightdiameter,leftheight+rightheight+2});
}
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);
    int height=0;
    cout<<Diameter(root,height)<<endl;//output=3
    return 0;
}







// 🔹 4. Maximum Path Sum in Binary Tree
// 🧠 Mathematical Definition
// MaxPathSum(T)=max(MaxPathSum(left),MaxPathSum(right),max(0,MaxPathSumFromNode(left))+max(0,MaxPathSumFromNode(right))+T.val)
// Base case:
// MaxPathSum(NULL)=0
// 🧠 Why max(0,...)?
// Because we want to maximize the path sum, and if the sum of a subtree is negative, we might as well ignore it and start a new path from the current node.
// 🔁 Dry Run (Small Example)
//     1
//    / \
//   2   3
// MaxPathSumFromNode(2)=2
// MaxPathSumFromNode(3)=3
// MaxPathSum(1)=max(2,3,2+3+1)=6
// ✔ Correct (path: 2→1→3)
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to calculate the maximum path sum.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Maximum Path Sum in Binary Tree





#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int MaxPathSumFromNode(Node* root,int &maxsum){
    if(root==NULL) return 0;
    int leftsum=max(0,(MaxPathSumFromNode(root->left,maxsum)));
    int rightsum=max(0,(MaxPathSumFromNode(root->right,maxsum)));
   int currentmax=leftsum+rightsum+root->val;
    maxsum=max(maxsum,currentmax);
    return max(leftsum,rightsum)+root->val;
}
int MaxPathSum(Node* root){
    int maxsum=INT_MIN;
    MaxPathSumFromNode(root,maxsum);
    return maxsum;
}
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);
    cout<<MaxPathSum(root)<<endl;//output=11 (path: 4→2→1→3)
    return 0;
}




// 🔹 5. Check if Tree is Balanced
// 🧠 Mathematical Definition
// A tree is balanced if for every node, the difference in height between its left and right subtrees is at most 1.
// Base case:
// A tree is balanced if for every node, the difference in height between its left and right subtrees is at most 1.
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to check if it is balanced and to calculate its height.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Check if Tree is Balanced


// ✅ Your Logic (Mathematical View)
// You are using:

// Height (T)=max(Height(left),Height(right))+1 and if unbalanced return -1

// And condition: if(abs(leftheight-rightheight)<=1) then balanced else unbalanced

// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CheckBalanced(Node* root)
// ✔ Base case
// if(root==NULL) return 0;

// 👉 Height of empty tree = 0 ✅

// ✔ Left subtree check
// int leftheight=CheckBalanced(root->left);
// if(leftheight==-1) return -1;

// 👉 If left subtree already unbalanced → stop early
// ✔ This is optimization (important)

// ✔ Right subtree check
// int rightheight=CheckBalanced(root->right);
// if(rightheight==-1) return -1;

// ✔ Same logic

// ✔ Balance condition
// if(abs(leftheight-rightheight)>1) return -1;

// ✔ Correct definition of balanced tree

// ✔ Return height
// return max(leftheight,rightheight)+1;

// ✔ Correct height calculation

// 🔹 Wrapper Function
// bool IsBalanced(Node* root){
//     return CheckBalanced(root)!=-1;
// }

// ✔ Perfect conversion to boolean

// 🔁 Dry Run (Your Tree)
//         1
//        / \
//       2   3
//      / \
//     4   5
// Heights:
// 4 → 0
// 5 → 0
// 2 → 1
// 3 → 0
// 1 → 2

// Check:
// ∣1−0∣=1≤1

// ✔ Balanced → Output = 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;
    }
};
int CheckBalanced(Node* root){
    if(root==NULL) return 0;
    int leftheight=CheckBalanced(root->left);
    if(leftheight==-1) return -1;
    int rightheight=CheckBalanced(root->right);
    if(rightheight==-1) return -1;
    if(abs(leftheight-rightheight)>1) return -1;
    return max(leftheight,rightheight)+1;
}
bool IsBalanced(Node* root){
    return CheckBalanced(root)!=-1;
}
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);
    cout<<IsBalanced(root)<<endl;//output=1 (true)
    return 0;
}






// 🔹 6. Check if Tree is Symmetric
// 🧠 Mathematical Definition
// A tree is symmetric if the left subtree is a mirror reflection of the right subtree.
// Base case:
// A tree is symmetric if the left subtree is a mirror reflection of the right subtree.
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to check if it is symmetric.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Check if Tree is Symmetric
// ✅ Your Logic (Mathematical View)
// You are using:
// Symmetric(T)=Symmetric(left,right)
// Base case:
// Symmetric(NULL,NULL)=true
// Symmetric(node1,node2)=false if one is NULL and the other is not
// Symmetric(node1,node2)=false if node1.val!=node2.val
// Symmetric(node1,node2)=Symmetric(node1.left,node2.right) and Symmetric(node1.right,node2.left) otherwise
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// bool CheckSymmetric(Node* left,Node* right){
// ✔ Base case 1
// if(left==NULL && right==NULL) return true;
// ✔ Base case 2
// if(left==NULL || right==NULL) return false;
// ✔ Value comparison
// if(left->val!=right->val) return false;
// ✔ Recursive calls
// return CheckSymmetric(left->left,right->right) && CheckSymmetric(left->right,right->left);
// }

// 🔹 Wrapper Function
// bool IsSymmetric(Node* root){
//     return CheckSymmetric(root,root);
// }
// ✔ Perfect symmetry check by comparing the tree with itself
// 🔁 Dry Run (Your Tree)
//         1
//        / \
//       2   2
//      / \
//     3   4
// CheckSymmetric(1,1) → CheckSymmetric(2,2) && CheckSymmetric(2,2)
// CheckSymmetric(2,2) → CheckSymmetric(3,4) && CheckSymmetric(4,3)
// CheckSymmetric(3,4) → false (values differ)
// ✔ Not symmetric → Output = 0 (false)
// 🔹 C++ Example: Check if Tree is Symmetric






#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 CheckSymmetric(Node* left,Node* right){
    if(left==NULL && right==NULL) return true;
    if(left==NULL || right==NULL) return false;
    if(left->val!=right->val)  return false;
    return CheckSymmetric(left->left,right->right) && CheckSymmetric(left->right,right->left);
}
bool IsSymmetric(Node*root){
    return CheckSymmetric(root,root);
}
int main(){
    Node* root=new Node(1);
    root->left=new Node(2);
    root->right=new Node(2);
    root->left->left= new Node(3);
    root->left->right= new Node(4);
    cout<<IsSymmetric(root)<<endl;//output=0 (false)
}







// 🔹 7. Binary Search (Recursion)
// 🧠 Mathematical Definition
// Binary Search(low,high):
// mid=low+(high-low)/2
// if arr[mid]==target return mid
// if target<arr[mid] return Binary Search(low,mid-1)
// if target>arr[mid] return Binary Search(mid+1,high)
// Base case:
// if low>high return -1 (target not found in the array)
// if arr[mid]==target return mid (target found at index mid)
// 🧠 Time Complexity: O(log n) where n is the number of elements in the array, because we are halving the search space at each step.
// 🧠 Space Complexity: O(log n) due to the recursive call stack. In the worst case (when the target is not found), the depth of the recursion will be log n.
// 🔹 C++ Example: Binary Search (Recursion)
// ✅ Your Logic (Mathematical View)
// You are using:
// BinarySearch(arr,low,high,target):
// mid=low+(high-low)/2
// if arr[mid]==target return mid
// if target<arr[mid] return BinarySearch(arr,low,mid-1,target)
// if target>arr[mid] return BinarySearch(arr,mid+1,high,target)
// Base case:
// if low>high return -1 (target not found in the array)
// if arr[mid]==target return mid (target found at index mid)
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int BinarySearch(vector<int>& arr,int low,int high,int target){
// ✔ Base case 1
// if(low>high) return -1;
// ✔ Base case 2
// int mid=low+(high-low)/2;
// if(arr[mid]==target) return mid;
// ✔ Recursive calls
// if(target<arr[mid]) return BinarySearch(arr,low,mid-1,target);
// return BinarySearch(arr,mid+1,high,target);
// }





#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int BinarySearch(vector<int>&arr,int low,int high,int target){
    if(low>high) return -1;
    int mid=low+(high-low)/2;
    if(arr[mid]==target) return mid;
    if(target<arr[mid]) return BinarySearch(arr,low,mid-1,target);
    return BinarySearch(arr,mid+1,high,target);
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int target;
    cin>>target;
    int result=BinarySearch(arr,0,n-1,target);
    if(result!=-1){
        cout<<"Element found at index: "<<result<<endl;
    } else {
        cout<<"Element not found in the array."<<endl;
    }
    return 0;
}






// 🔹 8. Count Nodes in Binary Tree
// 🧠 Mathematical Definition
// CountNodes(T)=CountNodes(left)+CountNodes(right)+1
// Base case:
// CountNodes(NULL)=0
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to count it.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Count Nodes in Binary Tree
// ✅ Your Logic (Mathematical View)
// You are using:
// CountNodes(T)=CountNodes(left)+CountNodes(right)+1
// Base case:
// CountNodes(NULL)=0
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CountNodes(Node* root){
// ✔ Base case
// if(root==NULL) return 0;
// ✔ Recursive calls
// return CountNodes(root->left)+CountNodes(root->right)+1;
// }
// 🔹 Wrapper Function (if needed)
// Not needed in this case, as the core function already returns the total count of nodes in the tree.
// 🔁 Dry Run (Your Tree)
//         1
//        / \
//       2   3
//      / \
//     4   5
// CountNodes(4) → 1
// CountNodes(5) → 1
// CountNodes(2) → 3
// CountNodes(3) → 1
// CountNodes(1) → 5
// ✔ Total nodes = 5 → Output = 5
// 🔹 C++ Example: Count Nodes in Binary Tree




#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int CountNodes(Node* root){
    if(root==NULL) return 0;
    return CountNodes(root->left)+CountNodes(root->right)+1;
}
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);
    cout<<CountNodes(root)<<endl;//output=5
    return 0;
}




// 🔹 9. Count Leaf Nodes in Binary Tree
// 🧠 Mathematical Definition
// CountLeafNodes(T)=CountLeafNodes(left)+CountLeafNodes(right)
// Base case:
// CountLeafNodes(NULL)=0
// CountLeafNodes(leaf)=1
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to check if it is a leaf and to count it.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Count Leaf Nodes in Binary Tree
// ✅ Your Logic (Mathematical View)
// You are using:
// CountLeafNodes(T)=CountLeafNodes(left)+CountLeafNodes(right)
// Base case:
// CountLeafNodes(NULL)=0
// CountLeafNodes(leaf)=1
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CountLeafNodes(Node* root){
// ✔ Base case 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;

    }
};
int CountLeafNodes(Node* root){
    if(root==NULL) return 0;
    if(root->left==NULL && root->right==NULL) return 1;
    return CountLeafNodes(root->left) + CountLeafNodes(root->right);
}
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);
    cout<<CountLeafNodes(root)<<endl;//output=3 (leaf nodes: 4, 5, 3)
    return 0;
}




// 🔹 10. Count Non-Leaf Nodes in Binary Tree
// 🧠 Mathematical Definition
// CountNonLeafNodes(T)=CountNonLeafNodes(left)+CountNonLeafNodes(right)+1
// Base case:
// CountNonLeafNodes(NULL)=0
// CountNonLeafNodes(leaf)=0
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to check if it is a non-leaf and to count it.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Count Non-Leaf Nodes in Binary Tree
// ✅ Your Logic (Mathematical View)
// You are using:
// CountNonLeafNodes(T)=CountNonLeafNodes(left)+CountNonLeafNodes(right)+1
// Base case:
// CountNonLeafNodes(NULL)=0
// CountNonLeafNodes(leaf)=0
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CountNonLeafNodes(Node* root){
// ✔ Base case 1
// if(root==NULL) return 0;
// ✔ Base case 2
// if(root->left==NULL && root->right==NULL) return 0;
// ✔ Recursive calls
// return CountNonLeafNodes(root->left)+CountNonLeafNodes(root->right)+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;
    }
};
int CountNonLeafNodes(Node* root){
    if(root==NULL) return 0;
    if(root->left==NULL && root->right==NULL) return 0;
    return CountNonLeafNodes(root->left)+ CountNonLeafNodes(root->right) +1;
}
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);
    cout<<CountNonLeafNodes(root)<<endl;//output=2 (non-leaf nodes: 1, 2)
    return 0;
}








// 🔹 11. Count Nodes at K-th Level in Binary Tree
// 🧠 Mathematical Definition
// CountNodesAtK(T,k)=CountNodesAtK(left,k-1)+CountNodesAtK(right,k-1)
// Base case:
// CountNodesAtK(NULL,k)=0
// CountNodesAtK(node,k)=1 if k==0 else 0
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to check if it is at the k-th level and to count it.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Count Nodes at K-th Level in Binary Tree
// ✅ Your Logic (Mathematical View)
// You are using:
// CountNodesAtK(T,k)=CountNodesAtK(left,k-1)+CountNodesAtK(right,k-1)
// Base case:
// CountNodesAtK(NULL,k)=0
// CountNodesAtK(node,k)=1 if k==0 else 0
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CountNodesAtK(Node* root,int k){
// ✔ Base case 1
// if(root==NULL) return 0;
// ✔ Base case 2
// if(k==0) return 1;
// ✔ Recursive calls
// return CountNodesAtK(root->left,k-1)+CountNodesAtK(root->right,k-1);
// }
// 🔹 Wrapper Function (if needed)
// Not needed in this case, as the core function already returns the count of nodes at the k-th level in the tree.
// 🔁 Dry Run (Your Tree)
//         1
//        / \
//       2   3
//      / \
//     4   5
// CountNodesAtK(1,0) → 1
// CountNodesAtK(1,1) → CountNodesAtK(2,0) + CountNodesAtK(3,0) → 1 + 1 = 2
// CountNodesAtK(1,2) → CountNodesAtK(2,1) + CountNodesAtK(3,1) → (CountNodesAtK(4,0) + CountNodesAtK(5,0)) + 0 → (1 + 1) + 0 = 2
// ✔ Nodes at level 0 = 1 (node: 1) → Output = 1
// ✔ Nodes at level 1 = 2 (nodes: 2, 3) → Output = 2
// ✔ Nodes at level 2 = 2 (nodes: 4, 5) → Output = 2
// 🔹 C++ Example: Count Nodes at K-th Level in Binary Tree




#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int CountNodesAtK(Node* root,int k){
    if(root==NULL) return 0;
    if(k==0) return 1;
    return CountNodesAtK(root->left,k-1) + CountNodesAtK(root->right,k-1);
}
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);
    cout<<CountNodesAtK(root,0)<<endl;//output=1 (node at level 0: 1)
    cout<<CountNodesAtK(root,1)<<endl;//output=2 (nodes at level 1: 2, 3)
    cout<<CountNodesAtK(root,2)<<endl;//output=2 (nodes at level 2: 4, 5)
    return 0;
}






// 🔹 12. Count Nodes in Complete Binary Tree
// 🧠 Mathematical Definition
// CountNodes(T)=2^h-1 where h is the height of the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🧠 Time Complexity: O(log^2 n) where n is the number of nodes in the tree, because we calculate the height of the tree in O(log n) time and then use it to calculate the number of nodes.
// 🧠 Space Complexity: O(log n) due to the recursive call stack when calculating the height of the tree. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Count Nodes in Complete Binary Tree
// ✅ Your Logic (Mathematical View)
// You are using:
// CountNodes(T)=2^h-1 where h is the height of the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CountNodes(Node* root){
// ✔ Base case 1
// if(root==NULL) return 0;
// ✔ Base case 2
// if(root->left==NULL && root->right==NULL) return 1;
// ✔ Height calculation
// int leftheight=0,rightheight=0;
// Node* left=root->left;
// while(left!=NULL){
// leftheight++;
// left=left->left;
// }
// Node* right=root->right;
// while(right!=NULL){
// rightheight++;
// right=right->right;
// }
// ✔ Check if left and right heights are equal
// if(leftheight==rightheight) return pow(2,leftheight+1)-1;
// ✔ If heights are equal, it's a perfect binary tree → use formula
// ✔ If heights are not equal, it's a complete binary tree → count nodes recursively
// return 1+CountNodes(root->left)+CountNodes(root->right);
// }
// 🔹 Wrapper Function (if needed)
// Not needed in this case, as the core function already returns the total count of nodes in the complete binary tree.
// 🔁 Dry Run (Your Tree)
//         1
//        / \
//       2   3
//      / \
//     4   5
// CountNodes(1) → leftheight=2, rightheight=2 → return 2^(2+1)-1=7
// ✔ Total nodes = 5 → Output = 5
// 🔹 C++ Example: Count Nodes in Complete Binary Tree




#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int CountNodes(Node* root){
    if(root==NULL) return 0;
    if(root->left==NULL && root->right==NULL) return 1;
    int leftheight=0,rightheight=0;
    Node* left=root->left;
    while(left!=NULL){
        leftheight++;
        left=left->left;
    }
    Node* right=root->right;
    while(right!=NULL){
        rightheight++;
        right=right->right;
    }
    if(leftheight==rightheight) return pow(2,leftheight+1)-1;
    return 1+CountNodes(root->left) + CountNodes(root->right);
}
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);
    cout<<CountNodes(root)<<endl;//output=5
    return 0;
}



// 🔹 13. Count Nodes in Perfect Binary Tree
// 2. Perfect Binary Tree ✅ (ONLY CASE WHERE FORMULA WORKS)
// 🔍 Example
//         1
//        / \
//       2   3
//      / \ / \
//     4  5 6  7
// Levels = 3
// Edges height = 2
// Using formulas:

// 🔥 Final Truth (Remember This)
// Height Type	Formula
// Levels	CountNodes(T)=2^h-1 where h is the number of levels in the tree
// Edges	CountNodes(T)=2^(h+1)-1 where h is the height of the tree in terms of edges
// CountNodes
// (T)=2^(h)-1 where h is the height of the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🧠 Time Complexity: O(log n) where n is the number of nodes in the tree, because we calculate the height of the tree in O(log n) time and then use it to calculate the number of nodes.
// 🧠 Space Complexity: O(log n) due to the recursive call stack when calculating the height of the tree. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Count Nodes in Perfect Binary Tree
// ✅ Your Logic (Mathematical View)
// You are using:
// CountNodes(T)=2^(h)-1 where h is the height of the tree

// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CountNodes(Node* root){
// ✔ Base case 1
// if(root==NULL) return 0;
// ✔ Base case 2
// if(root->left==NULL && root->right==NULL) return 1;
// ✔ Height calculation
// int height=0;
// Node* current=root;
// while(current!=NULL){
// height++;
// current=current->left;
// }
// ✔ Mathematical Formula
// return (1 << height) - 1; // Using bit shifting for 2^height - 1
// }
// 🔹 Wrapper Function (if needed)
// Not needed in this case, as the core function already returns the total count of nodes in the perfect binary tree.
// 🔁 Dry Run (Your Tree)





#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int leftHeight(Node* root){
    int height=0;
    while(root!=NULL){;
        root=root->left;
        height++;
    }
    return height;
}
int rightHeight(Node* root){
    int height=0;
    while(root!=NULL){
        root=root->right;
        height++;
    }
    return height;
}
int CountNodes(Node* root){
  if(root==NULL) return 0;
  int leftheight=leftHeight(root);
  int rightheight=rightHeight(root);
  if(leftheight==rightheight){
    return (1<<leftheight)-1;
  }
  return 1+CountNodes(root->left)+CountNodes(root->right);
}
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);
    cout<<CountNodes(root)<<endl;//output=5
    return 0;
}










// 🔹 14. Count Nodes in Full Binary Tree
// 🧠 Mathematical Definition
// CountNodes(T)=2*h+1 where h is the height of the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to count it.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Count Nodes in Full Binary Tree
// ✅ Your Logic (Mathematical View)
// You are using:
// CountNodes(T)=2*h+1 where h is the height of the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CountNodes(Node* root){
// ✔ Base case 1
// if(root==NULL) return 0;
// ✔ Base case 2
// if(root->left==NULL && root->right==NULL) return 1;
// ✔ Height calculation
// int height=0;
// Node* current=root;
// while(current!=NULL){
// height++;
// current=current->left;
// }
// ✔ Mathematical Formula
// return 2*height+1;
// }
// 🔹 Wrapper Function (if needed)
// Not needed in this case, as the core function already returns the total count of nodes in the full binary tree.
// 🔁 Dry Run (Your Tree)



#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int CountNodes(Node* root){
    if(root==NULL) return 0;
     if(root->left == NULL && root->right == NULL) return 1;

     int leftheight = 0, rightheight = 0;
     Node* left = root->left;
     while(left != NULL){
         leftheight++;
         left = left->left;
     }
     Node* right = root->right;
     while(right != NULL){
         rightheight++;
         right = right->right;
     }
     if(leftheight == rightheight) return (1 << (leftheight + 1)) - 1; // Using bit shifting for 2^(leftheight + 1) - 1
    return 1 + CountNodes(root->left) + CountNodes(root->right);
}

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);
    cout<<CountNodes(root)<<endl;//output=5
    return 0;
}




// 🔹 15. Count Nodes in Binary Tree with N Nodes
// 🧠 Mathematical Definition
// CountNodes(T)=N where N is the total number of nodes in the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to count it.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Count Nodes in Binary Tree with N Nodes
// ✅ Your Logic (Mathematical View)
// You are using:
// CountNodes(T)=N where N is the total number of nodes in the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CountNodes(Node* root){
// ✔ Base case 1
// if(root==NULL) return 0;
// ✔ Base case 2
// if(root->left==NULL && root->right==NULL) return 1;
// ✔ Recursive calls
// return CountNodes(root->left)+CountNodes(root->right)+1;
// }
// 🔹 Wrapper Function (if needed)
// Not needed in this case, as the core function already returns the total count of nodes in the binary tree.
// 🔁 Dry Run (Your Tree)
//         1
//        / \
//       2   3
//      / \
//     4   5
// CountNodes(4) → 1
// CountNodes(5) → 1
// CountNodes(2) → 3
// CountNodes(3) → 1
// CountNodes(1) → 5
// ✔ Total nodes = 5 → Output = 5
// 🔹 C++ Example: Count Nodes in Binary Tree with N Nodes



#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int CountNodes(Node* root){
    if(root==NULL) return 0;
    return CountNodes(root->left) + CountNodes(root->right) +1;
}
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);
    cout<<CountNodes(root)<<endl;//output=5
    return 0;
}


// 🔹 16. Count Nodes in Binary Tree with L Leaves
// 🧠 Mathematical Definition
// CountNodes(T)=2*L-1 where L is the total number of leaf nodes in the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to count the leaf nodes and then calculate the total number of nodes.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Count Nodes in Binary Tree with L Leaves
// ✅ Your Logic (Mathematical View)
// You are using:
// CountNodes(T)=2*L-1 where L is the total number of leaf nodes in the tree
// Base case:
// CountNodes(NULL)=0
// CountNodes(leaf)=1
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// int CountNodes(Node* root){
// ✔ Base case 1
// if(root==NULL) return 0;
// ✔ Base case 2
// if(root->left==NULL && root->right==NULL) return 1;
// ✔ Recursive calls to count leaf nodes
// int leftLeaves=CountNodes(root->left);
// int rightLeaves=CountNodes(root->right);
// ✔ Total leaf nodes
// int totalLeaves=leftLeaves+rightLeaves;
// ✔ Mathematical Formula to calculate total nodes from leaf nodes
// return 2*totalLeaves-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;
    }
};
int CountNodes(Node* root){
    if(root==NULL) return 0;
    if(root->left==NULL && root->right==NULL) return 1;
    int leftleaves=CountNodes(root->left);
    int rightleaves=CountNodes(root->right);
    return 2*(leftleaves+rightleaves)-1;
}
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);
    cout<<CountNodes(root)<<endl;//output=5 (leaf nodes: 4,5, 3)
    return 0;
}






// 🔹 16. Sum of Nodes
// 🧠 Mathematical Formula
// Sum(T)=Sum(left)+Sum(right)+root->val
// Base case:
// Sum(NULL)=0
// 🧠 Time Complexity: O(n) where n is the number of nodes in the
// tree, because we visit each node once to calculate the sum.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Sum of Nodes
// ✅ Your Logic (Mathematical View)
// You are using:
// Sum(T)=Sum(left)+Sum(right)+root->val




#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val= data;
        left=NULL;
        right=NULL;
    }
};
int sumOfNodes(Node* root){
    if(root==NULL) return 0;
    return sumOfNodes(root->left)+sumOfNodes(root->right)+root->val;
}
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);
    cout<<sumOfNodes(root)<<endl;//output=15 (1+2+3+4+5)
    return 0;
}





// 🔹 17. Maximum Value in Tree
// 🧠 Mathematical Formula
// Max(T)=max(root,Max(left),Max(right))
// Base case:
// Max(NULL)=INT_MIN (or a very small value to indicate no nodes)
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to compare its value with the maximum values from left and right subtrees.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Maximum Value in Tree
// ✅ Your Logic (Mathematical View)




#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int Max(Node* root){
    if(root==NULL) return INT_MIN;
    return max(root->val, max(Max(root->left), Max(root->right)));
}
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(9);
    cout<<Max(root)<<endl;//output=9 (maximum value in the tree)
    return 0;
}




// 🔹 18. Minimum Value in Tree
// 🧠 Formula
// Min(T)=min(root,Min(left),Min(right))
// Base case:
// Min(NULL)=INT_MAX (or a very large value to indicate no nodes)
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to compare its value with the minimum values from left and right subtrees.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).




#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
int Min(Node* root){
    if(root==NULL) return INT_MAX;
    return min(root->val,min(Min(root->left),Min(root->right)));
}
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(-1);
    cout<<Min(root)<<endl;//output=-1 (minimum value in the tree)
    return 0;
}



// 🔹 19. Path-Based Problems ⭐⭐⭐
// 🔸 (a) Root to Node Path
// 🧠 Mathematical Definition
// RootToNodePath(T,target)=RootToNodePath(left,target) OR RootToNodePath(right,target) OR (root if root==target)
// Base case:
// RootToNodePath(NULL,target)=false
// RootToNodePath(node,target)=true if node->val==target else false
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to check if it is the target and to build the path.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack and the space used to store the path. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Root to Node Path
// ✅ Your Logic (Mathematical View)
// You are using:
// RootToNodePath(T,target)=RootToNodePath(left,target) OR RootToNodePath(right,target) OR (root if root==target)
// Base case:


#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 RootToNodePath(Node* root,int target,vector<int>& path){
    if(root==NULL) return false;
    path.push_back(root->val);
    if(root->val==target) return true;
    if(RootToNodePath(root->left,target,path) || RootToNodePath(root->right,target,path)) return true;
    path.pop_back();
    return false;
}
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);
    vector<int>path;
    int target=3;
    if(RootToNodePath(root,target,path)){
        cout<<"Path from root to node "<<target<<": ";
        for(int val:path){
            cout<<val<<" ";
        }
        cout<<endl;
    } else {
        cout<<"Node "<<target<<" not found in the tree."<<endl;
    }

}




// 🔸 (b) Node to Root Path
// 🧠 Mathematical Definition
// NodeToRootPath(T,target)=NodeToRootPath(left,target) OR NodeToRootPath(right,target) OR (root if root==target)
// Base case:
// NodeToRootPath(NULL,target)=false
// NodeToRootPath(node,target)=true if node->val==target else false
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to check if it is the target and to build the path.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack and the space used to store the path. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Node to Root Path
// ✅ Your Logic (Mathematical View)
// You are using:
// NodeToRootPath(T,target)=NodeToRootPath(left,target) OR NodeToRootPath(right,target) OR (root if root==target)
// Base case:
// NodeToRootPath(NULL,target)=false
// NodeToRootPath(node,target)=true if node->val==target else false
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// bool NodeToRootPath(Node* root,int target,vector<int>& path){
// ✔ Base case 1
// if(root==NULL) return false;
// ✔ Base case 2
// if(root->val==target) return true;
// ✔ Recursive calls to find target in left and right subtrees
// if(NodeToRootPath(root->left,target,path) || NodeToRootPath(root->right,target,path)) return true;
// ✔ If target is found in left or right subtree, add current node to path


#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 NodeToRootPath(Node* root,int target,vector<int>&path){
    if(root==NULL) return false;
    if(root->val==target) return true;
    if(NodeToRootPath(root->left,target,path) || NodeToRootPath(root->right,target,path)){
        path.push_back(root->val);
        return true;
    }
    return false;
}
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);
    vector<int>path;
    int target=5;
    if(NodeToRootPath(root,target,path)){
        cout<<"path from node "<<target<<" to root: ";
        for(int i=path.size()-1;i>=0;i--){
            cout<<path[i]<<" ";
        }
        cout<<endl;
    } else {
        cout<<"Node "<<target<<" not found in the tree."<<endl;
    }
}




//(b) Path Sum
// 🧠 Mathematical Definition
// PathSum(T,target)=PathSum(left,target-root->val) OR PathSum(right,target-root->val) OR (true if root->val==target else false)
// Base case:
// PathSum(NULL,target)=false
// PathSum(node,target)=true if node->val==target else false
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to check if it is part of a path that sums to the target.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: Path Sum
// ✅ Your Logic (Mathematical View)
// You are using:
// PathSum(T,target)=PathSum(left,target-root->val) OR PathSum(right,target-root->val) OR (true if root->val==target 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 PathSum(Node* root,int target){
    if(root==NULL) return false;
    if(root->val==target) return true;
    return PathSum(root->left,target-root->val)|| PathSum(root->right,target-root->val);
}
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);
    int target=17;
    if(PathSum(root,target)){
        cout<<"There is a path in the tree that sums to "<<target<<endl;
    } else {
        cout<<"There is no path in the tree that sums to "<<target<<endl;
    }
     return 0;
}



// 🔹 3. LCA (Lowest Common Ancestor) ⭐⭐⭐
// 🧠 Idea
// If left and right both return non-null → current is LCA
// If left is null → return right
// If right is null → return left
// Base case:
// LCA(NULL,target1,target2)=NULL
// LCA(node,target1,target2)=node if node->val==target1 or node->val==target2 else NULL
// 🧠 Time Complexity: O(n) where n is the number of nodes in the
// tree, because we visit each node once to check if it is the LCA of the two target nodes.
// 🧠 Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this can be O(n).
// 🔹 C++ Example: LCA (Lowest Common Ancestor)
// ✅ Your Logic (Mathematical View)







#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* LCA(Node* root,int target1,int target2){
    if(root==NULL) return NULL;
    if(root->val==target1 || root->val==target2) return root;
    Node* left=LCA(root->left,target1,target2);
    Node* right=LCA(root->right,target1,target2);
    if(left!=NULL && right!=NULL) return root;
    if(left!=NULL) return left;
    return right;
}
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);
    int target1=4,target2=5;
    Node* lca=LCA(root,target1,target2);
    if(lca!=NULL){
        cout<<"LCA of "<<target1<<" and "<<target2<<" is: "<<lca->val<<endl;//output=2
    } else {
        cout<<"LCA does not exist for "<<target1<<" and "<<target2<<endl;
    }
}



//🔹 5. Zig-Zag Traversal
// 🧠 Idea
// Use a queue for level order traversal and a boolean flag to indicate the direction of traversal (left to right or right to left).
// Base case:
// ZigZagTraversal(NULL)=empty list
// ZigZagTraversal(node)=list containing node->val
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to add it to the zig-zag traversal list.
// 🧠 Space Complexity: O(w) where w is the maximum width of the tree, due to the queue used for level order traversal. In the worst case (complete binary tree), this can be O(n/2) = O(n).
// 🔹 C++ Example: Zig-Zag Traversal
// ✅ Your Logic (Mathematical View)
// You are using:
// ZigZagTraversal(NULL)=empty list
// ZigZagTraversal(node)=list containing node->val
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// vector<vector<int>> ZigZagTraversal(Node* root){
// ✔ Base case
// if(root==NULL) return {};
// ✔ Initialize data structures
// vector<vector<int>> result;
// queue<Node*> q;
// q.push(root);
// bool leftToRight=true;
// ✔ Level order traversal with zig-zag pattern
// while(!q.empty()){
// int size=q.size();
// vector<int> level(size);
// for(int i=0;i<size;i++){
// Node* current=q.front();
// q.pop();
// int index= leftToRight ? i : (size-1-i);
// level[index]=current->val;
// if(current->left!=NULL) q.push(current->left);
// if(current->right!=NULL) q.push(current->right);
// }
// leftToRight=!leftToRight;




#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int data){
        val=data;
        left=NULL;
        right=NULL;
    }
};
vector<vector<int>>ZigZagTraversal(Node* root){
    if(root==NULL) return {};
    vector<vector<int>>result;
    queue<Node*>q;
    q.push(root);
    bool leftToRight=true;
    while(!q.empty()){
        int size=q.size();
        vector<int>level(size);
        for(int i=0;i<size;i++){
            Node* current=q.front();
            q.pop();
            int index= leftToRight ? i : (size-1-i);
            level[index]=current->val;
            if(current->left!=NULL) q.push(current->left);
            if(current->right!=NULL) q.push(current->right);
        }
        result.push_back(level);
        leftToRight=!leftToRight;
    }
    return result;
}
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);
    vector<vector<int>>zigzag=ZigZagTraversal(root);
    cout<<"Zig-Zag Traversal: "<<endl;
    for(const auto& level:zigzag){
        for(int val:level){
            cout<<val<<" ";
        }
        cout<<endl;
    }
    return 0;
}



// 🔹 4. Tree Views
// 🔸 Right View
// 🧠 Idea
// Use level order traversal and print the last node of each level.
// Base case:
// RightView(NULL)=empty list
// RightView(node)=list containing node->val
// 🧠 Time Complexity: O(n) where n is the number of nodes in the tree, because we visit each node once to determine if it is the last node of its level.
// 🧠 Space Complexity: O(w) where w is the maximum width of the tree, due to the queue used for level order traversal. In the worst case (complete binary tree), this can be O(n/2) = O(n).
// 🔹 C++ Example: Right View
// ✅ Your Logic (Mathematical View)
// You are using:
// RightView(NULL)=empty list
// RightView(node)=list containing node->val
// 🔍 Step-by-Step Validation
// 🔹 Your Core Function
// vector<int> RightView(Node* root){
// ✔ Base case
// if(root==NULL) return {};
// ✔ Initialize data structures
// vector<int> result;
// queue<Node*> q;
// q.push(root);
// ✔ Level order traversal to get right view
// while(!q.empty()){
// int size=q.size();
// for(int i=0;i<size;i++){
// Node* current=q.front();
// q.pop();
// if(i==size-1) result.push_back(current->val);
// if(current->left!=NULL) q.push(current->left);
// if(current->right!=NULL) q.push(current->right);
// }
// }
// return result;
// }
// 🔹 Wrapper Function (if needed
// Not needed in this case, as the core function already returns the right view of the tree.
// 🔁 Dry Run (Your Tree)
//         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;

    }
};
vector<int> RightView(Node* root){
    if(root==NULL) return {};
    vector<int>result;
    queue<Node*>q;
    q.push(root);
    while(!q.empty()){
        int size=q.size();
        for(int i=0;i<size;i++){
            Node* current=q.front();
            q.pop();
            if(i==size-1) result.push_back(current->val);
            if(current->left!=NULL) q.push(current->left);
            if(current->right!=NULL) q.push(current->right);
        }

    }
    return result;
}
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);
    vector<int>rightview(RightView(root));
    cout<<"Right View: ";
    for(int val: RightView(root)){
        cout<<val<<" ";
    }
    cout<<endl;
    return 0;
}