//optml soln using itera on

vector<vector<int>> getTreeTraversal(TreeNode *root){

vector<int> pre, in, post; //optml soln using recursion
if (root == NULL) { void inOrderTraversal(TreeNode* root, vector<int> &inOrder) {
return {}; if (root == NULL) return;
} inOrderTraversal(root->le , inOrder);
stack<pair<TreeNode *, int>> st; inOrder.push_back(root->data);
st.push({root, 1}); inOrderTraversal(root->right, inOrder);
}
while (!st.empty()) {
auto it = st.top(); void preOrderTraversal(TreeNode* root, vector<int> &preOrder) {
st.pop(); if (root == NULL) return;
preOrder.push_back(root->data);
if (it.second == 1) { preOrderTraversal(root->le , preOrder);
pre.push_back(it.first->data); preOrderTraversal(root->right, preOrder);
it.second = 2; }
st.push(it);
if (it.first->le != NULL) { void postOrderTraversal(TreeNode* root, vector<int> &postOrder) {
st.push({it.first->le , 1}); if (root == NULL) return;
} postOrderTraversal(root->le , postOrder);
} postOrderTraversal(root->right, postOrder);
else if (it.second == 2) { postOrder.push_back(root->data);
in.push_back(it.first->data); }
it.second = 3;
st.push(it); vector<vector<int>> getTreeTraversal(TreeNode *root) {
vector<int> inOrder, preOrder, postOrder;
if (it.first->right != NULL) { vector<vector<int>> ans;
st.push({it.first->right, 1});
} inOrderTraversal(root, inOrder);
} preOrderTraversal(root, preOrder);
postOrderTraversal(root, postOrder);
else {
post.push_back(it.first->data); ans.push_back(inOrder);
} ans.push_back(preOrder);
} ans.push_back(postOrder);

vector<vector<int>> result; return ans;

result.push_back(in); }
result.push_back(pre);
result.push_back(post);
return result;
}
// diff in leetcode and gfg soln is leetcode output is 2d vector where gfg's is
1d vector, also in case of overlapping of 2 nodes gfg one asks it in le to
right order whereas leetcode ask them to be in sorted order,thats why we
have to track height and width of that node , which makes leetcode soln
complicated and invloves complex logic.

//optml soln for leetcode

class Solu on {
public: //op mal code for GFG
vector<vector<int>> ver calTraversal(TreeNode* root) { class Solu on
map<int, map<int, mul set<int>>> nodes; {
queue<pair<TreeNode*, pair<int, int>>> todo; public:
//Func on to find the ver cal order traversal of Binary Tree.
todo.push({root, {0, 0}}); vector<int> ver calOrder(Node *root)
{
while (!todo.empty()) { queue<pair<Node*,int>> que;
auto p = todo.front(); vector<int> ans;
todo.pop(); map<int,vector<int>> mpp;
TreeNode* temp = p.first; que.push({root,0});
while(que.size()){
int x = p.second.first; Node* temp=que.front().first;
int y = p.second.second; int line=que.front().second;
que.pop();
nodes[x][y].insert(temp->val); if(temp->le ){
que.push({temp->le ,line-1});
if (temp->le ) { }
todo.push({temp->le , {x - 1, y + 1}}); if(temp->right){
} que.push({temp->right,line+1});
}
if (temp->right) { mpp[line].push_back(temp->data);
todo.push({temp->right, {x + 1, y + 1}}); }
} for(auto i:mpp){
} for(auto j:i.second){
vector<vector<int>> ans; ans.push_back(j);
for(auto p: nodes){ }
vector<int> col; }
for(auto q: p.second){ return ans;
col.insert(col.end(), q.second.begin(), q.second.end()); }
} };
ans.push_back(col);
}
return ans;
}
};
//brute force (filling path in 2 diff arrays and returning last common /optml soln
element) class Solu on {
class Solu on { public:
public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p,
bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& TreeNode* q) {
path) { if(root==NULL || root==p || root==q){
if (root == NULL) { return root;
return false; }
} TreeNode* le =lowestCommonAncestor(root->le , p, q);
path.push_back(root); TreeNode* right=lowestCommonAncestor(root->right, p, q);
if (root == target) { if(le ==NULL){
return true; return right;
} }
if (findPath(root->le , target, path) || findPath(root->right, target, else if(right==NULL){
path)) { return le ;
return true; }
} else{
path.pop_back(); return root;
return false; }
} }
};
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p,
TreeNode* q) {
vector<TreeNode*> pathP, pathQ;
if (!findPath(root, p, pathP) || !findPath(root, q, pathQ)) {
return NULL;
}
int i = 0;
while (i < pathP.size() && i < pathQ.size() && pathP[i] == pathQ[i]) {
i++;
}
return pathP[i - 1];
}
};