Step-By-Step Directions From a Binary Tree Node to Another | 2 Approaches | Leetcode 2096
Вставка
- Опубліковано 25 сер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 46th Video of our Playlist "BINARY TREE : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good Tree Problem : Step-By-Step Directions From a Binary Tree Node to Another| 2 Approaches | Leetcode 2096 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Step-By-Step Directions From a Binary Tree Node to Another| 2 Approaches | Leetcode 2096 | codestorywithMIK
Company Tags : AMAZON
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1 (Using LCA)
Time Complexity: O(n)
Space Complexity: O(n)
Description:
Lowest Common Ancestor (LCA): Find the LCA of the startValue and destValue nodes using a recursive approach. The LCA is the node that is an ancestor to both target nodes and is farthest from the root.
Find Paths: From the LCA, find paths to both startValue and destValue. These paths are recorded as sequences of 'L' (left) and 'R' (right).
Construct Result: Convert the path from LCA to startValue to 'U' (upward moves) and append the path from LCA to destValue directly to form the result.
Steps:
Find the LCA of startValue and destValue.
Find the path from the LCA to startValue and destValue.
Construct the result by moving up from startValue to LCA and then following the path to destValue.
Approach 2 (Without finding LCA)
Time Complexity: O(n)
Space Complexity: O(n)
Description:
Find Paths: Find paths from the root to both startValue and destValue directly. These paths are recorded as sequences of 'L' (left) and 'R' (right).
Identify Common Path: Determine the common path prefix between the two paths.
Construct Result: From the point where the paths diverge, convert the path from the common ancestor to startValue to 'U' (upward moves) and append the remaining path to destValue directly to form the result.
Steps:
Find the path from the root to startValue and destValue.
Identify the length of the common path prefix.
Construct the result by moving up from startValue to the common ancestor and then following the path to destValue.
Both approaches efficiently determine the sequence of moves required to navigate from startValue to destValue in a binary tree, with the first approach leveraging the concept of LCA and the second approach avoiding explicit LCA computation by directly comparing paths from the root.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
Loved the optimization ! Thanks for all the efforts and helping us grow. Recently promoted to knight on leetcode with the help of your videos 💙💙💯💯
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue) {
return helper(root,startValue,destValue);
}
public TreeNode findNode(int value, TreeNode root){
if(root == null){
return null;
}
if(root.val == value){
return root;
}
TreeNode left = findNode(value,root.left);
if(left != null){
return left;
}
return findNode(value,root.right);
}
public String helper(TreeNode root, int start, int end){
HashMap parentMap = new HashMap();
function(root,null,parentMap);
Queue queue = new LinkedList();
TreeNode startNode = findNode(start,root);
TreeNode endNode = findNode(end,root);
queue.add(new Pair(startNode,""));
Set visited = new HashSet();
while(!queue.isEmpty()){
Pair rem = queue.poll();
if(visited.contains(rem.node.val)){
continue;
}
if(rem.node.val == end){
return rem.psf;
}
visited.add(rem.node.val);
if(rem.node.left != null && !visited.contains(rem.node.left.val)){
queue.add(new Pair(rem.node.left,rem.psf + "L"));
}
if(rem.node.right != null && !visited.contains(rem.node.right.val)){
queue.add(new Pair(rem.node.right,rem.psf + "R"));
}
TreeNode parentN = parentMap.get(rem.node);
if(parentN!= null && !visited.contains(parentN.val)){
queue.add(new Pair(parentN,rem.psf + "U"));
}
}
return "";
}
public void function(TreeNode root,TreeNode parent, HashMap parentMap){
if(root == null){
return;
}
parentMap.put(root,parent);
function(root.left,root,parentMap);
function(root.right,root,parentMap);
}
}
class Pair{
TreeNode node;
String psf;
public Pair(TreeNode node, String psf){
this.node = node;
this.psf = psf;
}
}
most underrated guy
Lowest Common Ancestor (LCA) video: ua-cam.com/video/Oi3_06ultic/v-deo.htmlfeature=shared
class Solution {
public:
int leafCount=0;
void formG(TreeNode* root,unordered_map&mp){
if(!root) return;
if(root->left==NULL && root->right==NULL){
leafCount++;
}
if(root->left!=NULL){
mp[root->val].push_back({root->left->val,'L'});
mp[root->left->val].push_back({root->val,'U'});
formG(root->left,mp);
}
if(root->right!=NULL){
mp[root->val].push_back({root->right->val,'R'});
mp[root->right->val].push_back({root->val,'U'});
formG(root->right,mp);
}
return;
}
string getDirections(TreeNode* root, int s, int d) {
unordered_mapmp;
formG(root,mp);
int n=mp.size()+leafCount;
vectorvisited(n+1,false);
vectorparent(n+1);
parent[s]={-1,'a'};
queueque;
que.push(s);
visited[s]=true;
while(!que.empty()){
int front=que.front();
que.pop();
for(auto &it:mp[front]){
if(!visited[it.first]){
visited[it.first]=true;
parent[it.first]={front,it.second};
que.push(it.first);
}
}
if(visited[d]){
break;
}
}
string result="";
int dest=d;
while(parent[dest].first!=-1){
result+=parent[dest].second;
dest=parent[dest].first;
}
reverse(begin(result),end(result));
return result;
}
};
codestorywithmik, so very much grateful for your support. Really appreciate it !!!!!!!!!!!.
Saw your video in the morning, here is my solution with first approach.
Please share your views on it.
❤❤
if(root->left!=NULL && root->right!=NULL){
leafCount++;
}.....this line should be if(root->left==NULL && root->right==NULL) know ..for the node to be leaf???
@@unknown47896yes u are correct
Although it worked
But it should be corrected
Thank you 👍
class Solution {
public:
void build(unordered_map& adj, set& visited, TreeNode* node) {
if(!node or visited.find(node -> val) != visited.end())
return;
visited.insert(node -> val);
if(node -> left) {
adj[node -> val].push_back({node -> left -> val, 'L'});
adj[node -> left -> val].push_back({node -> val, 'U'});
build(adj, visited, node -> left);
}
if(node -> right) {
adj[node -> val].push_back({node -> right -> val, 'R'});
adj[node -> right -> val].push_back({node -> val, 'U'});
build(adj, visited, node -> right);
}
}
string getDirections(TreeNode* root, int start, int dest) {
unordered_map adj;
set visited;
build(adj, visited, root);
queue q;
visited.clear();
q.push({start, ""});
visited.insert(start);
while(!q.empty()) {
int node = q.front().first;
string s = q.front().second;
q.pop();
if(node == dest)
return s;
for(auto adjNode : adj[node]) {
if(visited.find(adjNode.first) == visited.end()) {
q.push({adjNode.first, s + adjNode.second});
visited.insert(adjNode.first);
}
}
}
return "";
}
};
/* Naive Approach */
/* Passes all Test cases */
class Solution {
static class Pair{
TreeNode node;
String dir;
Pair(TreeNode n, String d){
this.node = n;
this.dir = d;
}
}
public void markParents(HashMap parent_track, TreeNode root){
Queue q = new ArrayDeque();
q.add(root);
while(!q.isEmpty()){
TreeNode curr = q.peek();
q.remove();
if(curr.left != null){
q.add(curr.left);
parent_track.put(curr.left, curr);
}
if(curr.right != null){
q.add(curr.right);
parent_track.put(curr.right, curr);
}
}
}
public TreeNode findStart(TreeNode root, int start){
if(root == null) return null;
if(root.val == start) return root;
TreeNode left = findStart(root.left, start);
if(left == null) {
TreeNode right = findStart(root.right, start);
return right;
}
return left;
}
public String getDirections(TreeNode root, int start, int dest) {
HashMap parent_track = new HashMap();
markParents(parent_track, root);
Queue q = new ArrayDeque();
HashSet vis = new HashSet();
TreeNode src = findStart(root, start);
q.add(new Pair(src, ""));
vis.add(src);
while(!q.isEmpty()){
int size = q.size();
for(int i = 0; i < size; i++){
TreeNode curNode = q.peek().node;
String curStr = q.peek().dir;
q.remove();
if(curNode.val == dest) return curStr;
if(parent_track.containsKey(curNode)){
TreeNode adj = parent_track.get(curNode);
if(!vis.contains(adj)){
q.add(new Pair(adj, curStr + "U"));
vis.add(adj);
}
}
if(curNode.left != null){
TreeNode adj = curNode.left;
if(!vis.contains(adj)){
q.add(new Pair(adj, curStr + "L"));
vis.add(adj);
}
}
if(curNode.right != null){
TreeNode adj = curNode.right;
if(!vis.contains(adj)){
q.add(new Pair(adj, curStr + "R"));
vis.add(adj);
}
}
}
}
return "";
}
}
suggest unique project ideas for placements in mern or dsa
bhai mile toh mujhe bhi batana
Mujhe bhi
are mile to batanaa kuch, mere pas ek bhi project nhi h shi se...
Cryptocurrency tracker?
Bhaiya please upload segment tree videos frequently because i was able to understand segment tree from you only
Like for more segment tree videos
Using BFS : Gives Memory Limit Exceeded
void createGraph(TreeNode* root, vector&adj, int &count) {
if(!root) return;
int curValue = root->val;
count++;
if(root->left) {
adj[curValue].push_back({root->left->val, 'L'});
adj[root->left->val].push_back({curValue, 'U'});
createGraph(root->left, adj, count);
}
if(root->right) {
adj[curValue].push_back({root->right->val, 'R'});
adj[root->right->val].push_back({curValue, 'U'});
createGraph(root->right, adj, count);
}
}
string getDirections(TreeNode* root, int startValue, int destValue) {
vectoradj(100001);
int n=0;
createGraph(root, adj, n);
queueq;
q.push({startValue, ""});
vectorvis(100001, 0);
string ans="";
while(!q.empty()) {
int node=q.front().first;
string dir=q.front().second;
q.pop();
vis[node]=1;
for(auto adjNode: adj[node]) {
if(!vis[adjNode.first]) {
if(adjNode.first == destValue) return dir+adjNode.second;
q.push({adjNode.first, dir+adjNode.second});
}
}
}
return ans;
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
class Pair{
int node;
String direction;
public Pair(int node , String direction){
this.node = node;
this.direction = direction;
}
@Override
public String toString() {
return "Pair{" +
"node=" + node +
", direction='" + direction + '\'' +
'}';
}
}
public String getDirections(TreeNode root, int startValue, int destValue) {
// Number of nodes
int n = countNodes(root);
// Creating Graph
List adj = new ArrayList();
for(int i = 0 ; i
I couldn’t think of the approach. But then 10 minutes in the video, I coded it up 😊. Thank you so much
class Solution {
public:
TreeNode*start;
TreeNode*des;
void preorder(TreeNode*root,unordered_map&m,int startValue, int destValue)
{
if(root==NULL)
return;
if(root->val == startValue) start = root;
if(root->val== destValue) des=root;
if(root->left)
{
m[root->left] = root;
preorder(root->left,m,startValue,destValue);
}
if(root->right)
{
m[root->right] = root;
preorder(root->right,m,startValue,destValue);
}
}
string getDirections(TreeNode* root, int startValue, int destValue)
{
unordered_map m;
preorder(root, m, startValue, destValue);
queue q;
unordered_map visited;
unordered_map path;
q.push(start);
visited[start] = 0;
path[start] = "";
while (!q.empty())
{
TreeNode* node = q.front();
q.pop();
if (node == des) return path[node];
if (node->left && visited.find(node->left) == visited.end())
{
visited[node->left] = visited[node] + 1;
path[node->left] = path[node] + "L";
q.push(node->left);
}
if (node->right && visited.find(node->right) == visited.end())
{
visited[node->right] = visited[node] + 1;
path[node->right] = path[node] + "R";
q.push(node->right);
}
if (m.find(node) != m.end() && visited.find(m[node]) == visited.end())
{
visited[m[node]] = visited[node] + 1;
path[m[node]] = path[node] + "U";
q.push(m[node]);
}
}
return "";
}
};
You explain things so well. I was able to code the 2nd approach on my own.
Now I also know about LCA
GRAPH APPROACH
TreeNode* findStart(TreeNode* root, int start, map &mp){
TreeNode* res = NULL;
queue q;
q.push(root);
mp[root] = NULL;
while(!q.empty()){
TreeNode* curr = q.front();
q.pop();
if(curr->val == start){
res = curr;
}
if(curr->left != NULL){
q.push(curr->left);
mp[curr->left] = curr;
}
if(curr->right != NULL){
q.push(curr->right);
mp[curr->right] = curr;
}
}
return res;
}
string getDirections(TreeNode* root, int startValue, int destValue){
map mp;
TreeNode* start = findStart(root, startValue, mp);
map visited;
queue q;
q.push({start, ""});
visited[start] = 1;
while(!q.empty()){
int n = q.size();
for(int i=0; ival == destValue){
return state;
}
if(curr->left != NULL && !visited[curr->left]){
q.push({curr->left, state+"L"});
visited[curr->left] = 1;
}
if(curr->right != NULL && !visited[curr->right]){
q.push({curr->right, state+"R"});
visited[curr->right] = 1;
}
if(mp[curr] && !visited[mp[curr]]){
q.push({mp[curr], state+"U"});
visited[mp[curr]] = 1;
}
}
}
return "";
}
bhaiya ek baar 3213 ki video upload kr dijiye(dp+trie)
Minimum cost wale ka optimal solution dp+trie se nhi hoga.
TLE de rha hai
Here's my solution to the problem (naive approach, getting memory limit exceed though)
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue) {
Map map = new HashMap();
constructMap(root, null, map);
Queue q = new LinkedList();
q.add(new Pair(startValue, new StringBuilder()));
Set set = new HashSet();
set.add(startValue);
while(!q.isEmpty()){
int size = q.size();
for(int i=0; i
I too followed similar approach , it was running for me
Step 1 -> Mapping parent to nodes (for taking of upward movement )
Step 2 -> getting starting and ending Nodes from value
Step3 -> Applying BFS Traversal iterate over tree and add Pair (node and string ) & returing once reached to destination.
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue) {
HashMap parentMap = new HashMap();
getParents(root, parentMap);
TreeNode startNode = getNode(root, startValue);
TreeNode endNode = getNode(root, destValue);
String ans = getPath(startNode, endNode, parentMap, "");
return ans;
}
public static void getParents(TreeNode root, HashMap parentMap) {
if (root == null) {
return;
}
if (root.left != null) {
parentMap.put(root.left, root);
getParents(root.left, parentMap);
}
if (root.right != null) {
parentMap.put(root.right, root);
getParents(root.right, parentMap);
}
}
public static TreeNode getNode(TreeNode root, int value) {
if (root == null) {
return null;
}
if (root.val == value) {
return root;
}
TreeNode l = getNode(root.left, value);
if (l == null) {
return getNode(root.right, value);
} else {
return l;
}
}
public static String getPath(TreeNode start, TreeNode end, HashMap parentMap, String s) {
Queue q = new LinkedList();
HashSet hs = new HashSet();
q.add(new Pair(start, ""));
hs.add(start);
while (!q.isEmpty()) {
Pair p = q.remove();
if (p.node.val == end.val) {
return p.s;
}
if (p.node.left != null && !hs.contains(p.node.left)) {
q.add(new Pair(p.node.left, p.s + "L"));
hs.add(p.node.left);
}
if (p.node.right != null && !hs.contains(p.node.right)) {
q.add(new Pair(p.node.right, p.s + "R"));
hs.add(p.node.right);
}
if (parentMap.get(p.node) != null && !hs.contains(parentMap.get(p.node))) {
q.add(new Pair(parentMap.get(p.node), p.s + "U"));
hs.add(parentMap.get(p.node));
}
}
return "";
}
}
class Pair {
TreeNode node;
String s;
public Pair(TreeNode node, String s) {
this.node = node;
this.s = s;
}
}
don't have idea in java but I have done in C++, and get same MLE, in my code I have add the path in the way( str += "L") but in C++ it always made copy and then again assign the previous string + latest character which tends to memory limit exceeded, Now, I have tried this like str.push_back('L') which doesn't create any copy and just added the character into the last of the string and doesn't giving any error. Maybe this will resolve your error.
MEMORY LIMIT EXCEEDED CODE -
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, int p, int q) {
if(root == NULL) return NULL;
if(root->val == p || root->val == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left != NULL && right != NULL) {
return root;
}
if(left == NULL) return right;
return left;
}
void inorder(TreeNode* root, int s, string temp, string &source) {
if(root) {
if(root->val == s) {
source = temp;
return ;
}
temp += "U";
inorder(root->left, s, temp, source);
inorder(root->right, s, temp, source);
}
}
void inorder1(TreeNode* root, int d, string temp, string &destination) {
if(root) {
if(root->val == d) {
destination = temp;
return ;
}
inorder1(root->left, d, temp + "L", destination);
inorder1(root->right, d, temp + "R", destination);
}
}
string getDirections(TreeNode* root, int s, int d) {
TreeNode* lca = lowestCommonAncestor(root, s, d);
string source = "";
string destination = "";
inorder(lca, s, "", source);
inorder1(lca, d, "", destination);
string ans = source + destination;
return ans;
}
};
CORRECT CODE -
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, int p, int q) {
if(root == NULL) return NULL;
if(root->val == p || root->val == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left != NULL && right != NULL) {
return root;
}
if(left == NULL) return right;
return left;
}
void inorder(TreeNode* root, int s, string& temp, string& source) {
if(root) {
if(root->val == s) {
source = temp;
return ;
}
temp.push_back('U');
inorder(root->left, s, temp, source);
temp.pop_back();
temp.push_back('U');
inorder(root->right, s, temp, source);
temp.pop_back();
}
}
void inorder1(TreeNode* root, int d, string& temp, string &destination) {
if(root) {
if(root->val == d) {
destination = temp;
return ;
}
temp.push_back('L');
inorder1(root->left, d, temp, destination);
temp.pop_back();
temp.push_back('R');
inorder1(root->right, d, temp, destination);
temp.pop_back();
}
}
string getDirections(TreeNode* root, int s, int d) {
TreeNode* lca = lowestCommonAncestor(root, s, d);
string source = "";
string destination = "";
string temp = "";
inorder(lca, s, temp, source);
temp = "";
inorder1(lca, d, temp, destination);
string ans = source + destination;
return ans;
}
};
hatsoff to the optimization
/* Naive Approach */
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue) {
// Creating graph
Map graph = new HashMap();
Set visited = new HashSet();
/* creating graph */
traverse(root, graph);
Queue q = new LinkedList();
q.add(new Node(startValue , ""));
visited.add(startValue);
while(q.size() > 0){
int size = q.size();
while(size --> 0){
Node temp = q.poll();
if(temp.val == destValue){
return temp.path;
}
for(Pair p : graph.get(temp.val)){
if(visited.contains(p.val)) continue;
q.add(new Node(p.val , temp.path + p.type));
visited.add(p.val);
}
}
}
return "";
}
void traverse(TreeNode root ,Map map ){
if(root == null){
return;
}
map.putIfAbsent(root.val , new ArrayList());
if(root.left != null){
map.putIfAbsent(root.left.val , new ArrayList());
/* adding parent to the child list */
map.get(root.left.val).add(new Pair(root.val , 'U'));
/* adding child to the parent list */
map.get(root.val).add(new Pair(root.left.val , 'L' ));
}
if(root.right != null){
map.putIfAbsent(root.right.val , new ArrayList());
/* adding parent to the child list */
map.get(root.right.val).add(new Pair(root.val , 'U'));
/* adding child to the parent list */
map.get(root.val).add(new Pair(root.right.val , 'R'));
}
traverse(root.left , map);
traverse(root.right , map);
}
}
class Node{
int val;
String path;
Node(int v , String p){
this.val = v;
this.path = p;
}
}
class Pair{
int val;
char type;
Pair(int val , char type ){
this.val = val;
this.type = type;
}
public String toString(){
return "[" + val + "," + type + "]";
}
}
Thank you bhaiya
C++ Fully Recursive Code
class Solution {
public:
string ans;
string solve(TreeNode* root, int ind, int &startValue, int &destValue) {
if (!root)
return "";
string left = solve(root->left, 1,startValue,destValue);
string right = solve(root->right, 2,startValue,destValue);
if (root->val == startValue) {
if (left.length()>0 && right.length() == 0) {
reverse(left.begin(), left.end());
ans = left;
}
else if (left.length()==0 && right.length() > 0) {
reverse(right.begin(), right.end());
ans = right;
}
else {
return "U";
}
} else if (root->val == destValue) {
if (left.length() + right.length() > 0) {
ans = (left.size()>0)? left:right;
} else {
return ((ind== 1) ? "L" : "R");
}
}
else{
if(ans.length()>0 || (left.length()==0 && right.size()==0)) return "";
else if(left.length()>0 && right.size()==0){
if(left[0]=='U'){
left+='U';
}
else{
left += ((ind== 1) ? "L" : "R");
}
return left;
}
else if(left.length()==0 && right.size()>0){
if(right[0]=='U'){
right+='U';
}
else{
right += ((ind== 1) ? "L" : "R");
}
return right;
}
else{
if(left[0]=='U'){
reverse(right.begin(),right.end());
left+=right;
ans=left;
}
else{
reverse(left.begin(),left.end());
right+=left;
ans=right;
}
}
}
return "";
}
string getDirections(TreeNode* root, int startValue, int destValue) {
ans = "";
solve(root, 0 ,startValue,destValue);
return ans;
}
};
class Solution {
TreeNode par[]=null;
class Pair{
String ans;
TreeNode node;
Pair(TreeNode t,String s){
node=t;
ans=s;
}
}
TreeNode findSource(TreeNode root,int s){
if(root==null)return null;
if(root.val==s)return root;
TreeNode left=findSource(root.left,s);
TreeNode right=findSource(root.right,s);
if(root.left!=null)par[root.left.val]=root;
if(root.right!=null)par[root.right.val]=root;
if(left==null)return right;
else return left;
}
public String getDirections(TreeNode node, int startValue, int destValue) {
par=new TreeNode[100000+1];
boolean vis[]=new boolean[100000+1];
Arrays.fill(par,null);
TreeNode src=findSource(node,startValue);
Queue q=new LinkedList();
q.add(new Pair(src,""));
vis[src.val]=true;
while(q.size()!=0){
Pair root=q.remove();
// if(vis[root.node.val]==true)continue;
// vis[root.node.val]=true;
if(root.node.val==destValue)return root.ans;
if(par[root.node.val]!=null && vis[par[root.node.val].val]==false){
q.add(new Pair(par[root.node.val],root.ans+"U"));
vis[root.node.val]=true;
}
if(root.node.left!=null && vis[root.node.left.val]==false){
q.add(new Pair(root.node.left,root.ans+"L"));
vis[root.node.left.val]=true;
}
if(root.node.right!=null && vis[root.node.right.val]==false){
q.add(new Pair(root.node.right,root.ans+"R"));
vis[root.node.right.val]=true;
}
}
return "";
}
}
GRAPH approach: (MLE)
class Solution {
public:
TreeNode* s;
TreeNode* t;
unordered_map parent;
void dfs(TreeNode* root, int& sv, int& dv) {
if (!root)
return;
if (root->left)
parent[root->left] = root;
if (root->right)
parent[root->right] = root;
if (root->val == sv)
s = root;
if (root->val == dv)
t = root;
dfs(root->left, sv, dv);
dfs(root->right, sv, dv);
}
string getDirections(TreeNode* root, int sv, int dv) {
dfs(root, sv, dv);
queue q;
q.push({s, ""});
unordered_set visited;
visited.insert(s);
while (!q.empty()) {
auto cur = q.front();
q.pop();
auto node = cur.first;
auto dir = cur.second;
if (node == t)
return dir;
if (node->left and visited.count(node->left) == 0) {
dir.push_back('L');
q.push({node->left, dir});
dir.pop_back();
visited.insert(node->left);
}
if (node->right and visited.count(node->right) == 0) {
dir.push_back('R');
q.push({node->right, dir});
dir.pop_back();
visited.insert(node->right);
}
if (parent.find(node) != parent.end() and
visited.count(parent[node]) == 0) {
dir.push_back('U');
q.push({parent[node], dir});
dir.pop_back();
visited.insert(parent[node]);
}
}
return "";
}
};
Naive APP:
void mappingParent(TreeNode * root, unordered_map&mp){
if(root==NULL) return;
if(root->left) mp[root->left]=root;
if(root->right) mp[root->right]=root;
mappingParent(root->left,mp);
mappingParent(root->right,mp);
}
TreeNode * inorder(TreeNode * root, int val){
if(root==NULL) return NULL;
if(root->val==val) return root;
TreeNode * left=inorder(root->left,val);
TreeNode * right= inorder(root->right,val);
if(left==NULL && right) return right;
if(right==NULL && left) return left;
return left;
}
void solve(TreeNode * root, TreeNode* e, string & path,string temp,unordered_map&mp,unordered_map&vis){
if(root==NULL || vis[root]==1) return;
vis[root]=1;
if(root->val==e->val){
path=temp;
return;
}
solve(root->left,e,path,temp+'L',mp,vis);
solve(root->right,e,path,temp+'R',mp,vis);
solve(mp[root],e,path,temp+'U',mp,vis);
}
string getDirections(TreeNode* root, int startValue, int destValue) {
string path="";
//mapping parent
unordered_mapmp;
mappingParent(root,mp);
TreeNode* s=inorder(root,startValue);
TreeNode* e=inorder(root,destValue);
unordered_mapvis;
solve(s,e,path,"",mp,vis);
return path;
}
Graph always challanges me.
Bhaiya I'm extremely sorry, I'm not able to do first approach said by you, because abhi bhi shortest path mene nehi shikha, mene apka graph concepts and questions wala playlist dekh raha hu, mein abhi DSU shikh raha hu, jab shortest path ho jaiga, tab mein try jarur karunga
@codestorywithMIK bhai please continue dp concept series specially partition dp that is tough
Good morning bhaiya😊❤
public static String call(TreeNode root , int start , int destination){
// first of all we need to make adj list
/// since we are not having information of how many node are available , so will use Map
Map map = new HashMap();
configureMap(root , map);
StringBuilder sb = new StringBuilder();
Queue q = new LinkedList();
q.offer(new Pair(start , sb));
Setvisited = new HashSet();
visited.add(start);
while(!q.isEmpty()){
int size = q.size();
for(int x = 0 ; x
i love your content but can you please suggest how to prepare aptitude
Thanks a lot bhaiya ❤❤
i dont know how, but i was able to think the dfs approach on my own, even before the bfs XD.
This is how i did it
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };\
*/
class Solution {
public:
TreeNode* solve(TreeNode* root, int p, int q){
if(root == NULL){
return NULL;
}
TreeNode* left = solve(root->left,p,q);
TreeNode* right = solve(root->right,p,q);
if(root->val == p){
return root;
}
if(root->val == q){
return root;
}
if(left != NULL && right != NULL){
return root;
}
if(left){
return left;
}
if(right){
return right;
}
return NULL;
}
bool build(int startNode,TreeNode* lca, bool reverse,string &path){
if(lca == NULL){
return 0;
}
if(startNode == lca->val){
return 1;
}
if(reverse){
path.push_back('U');
bool left = build(startNode,lca->left,reverse,path);
if(left){
return 1;
}
path.pop_back();
path.push_back('U');
bool right = build(startNode,lca->right,reverse,path);
if(right){
return 1;
}
path.pop_back();
}
else{
path.push_back('L');
bool left = build(startNode,lca->left,reverse,path);
if(left){
return 1;
}
path.pop_back();
path.push_back('R');
bool right = build(startNode,lca->right,reverse,path);
if(right){
return 1;
}
path.pop_back();
}
return 0;
}
string getDirections(TreeNode* root, int startValue, int destValue) {
TreeNode*lca = solve(root,startValue,destValue);
// now build the path from start to lca
string path = "";
build(startValue,lca,true,path);
build(destValue,lca,false,path);
return path;
}
};
As usual Thank you
Okay bhaiya HW done with graph...
class Solution {
public:
//number of nodes pata krne k liye
void dfs(TreeNode* root,int &n)
{
if(root==NULL)return;
dfs(root->left,n);
n++;
dfs(root->right,n);
}
void createGraph(vectoradj[],TreeNode* root)
{
if(root==NULL)return ;
if(root->left)
{
int value=root->val;
int leftVal=root->left->val;
adj[value].push_back({leftVal,'L'});
adj[leftVal].push_back({value,'U'});
createGraph(adj,root->left);
}
if(root->right)
{
int value=root->val;
int rightVal=root->right->val;
adj[value].push_back({rightVal,'R'});
adj[rightVal].push_back({value,'U'});
createGraph(adj,root->right);
}
}
string getDirections(TreeNode* root, int start, int dest)
{
//create graph
//for creating graph we first need to know number of nodes
int n;
dfs(root,n);
vectoradj[n+1];
createGraph(adj,root);
vectorvis(n+1,0);
vectorpath(n+1,-1);
vectordir(n+1);
queueq;
q.push(start);
vis[start]=1;
path[start]=-1;
while(!q.empty())
{
int node=q.front();
q.pop();
if(node==dest)break;
for(auto it:adj[node])
{
int adjNode=it.first;
char adjDir=it.second;
if(!vis[adjNode])
{
vis[adjNode]=1;
path[adjNode]=node;
dir[adjNode]=adjDir;
q.push(adjNode);
}
}
}
string ans="";
while(path[dest]!=-1)
{
ans+=dir[dest];
dest=path[dest];
}
reverse(ans.begin(),ans.end());
return ans;
}
};
n ka initial value define karo bhai,aur dfs function mae condition dalo ,if (root>left!=null),if (root->right!=null)
@@someshnayakrollno.-09sec-b27 yeah i should have defined the initial value of 'n' .My bad .🥲....But the second thing u r telling about condiiton of "if (root>left!=null),if (root->right!=null)" ....bhai actually in this Inorder traversal we dont need this condition as already i have put on the condition for "if(root==NULL)return;" and when it will come back from the child then only value of n will increase ...
and my code is working fine for all test cases.....
oh nice . 👌👌👌
Please make a video on "Russian Doll Envelopes" problem. I am getting stuck in that.
GRAPH APPROACH :
I HAVE DONE HW, 1. make graph 2. bfs to finds the path
but it got MEMORY LIMIT EXCEED!
how to fix it?
there is no Optimization using GRAPH + BFS ?
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public static void dfs(TreeNode root, Map map) {
if (root == null) {
return;
}
int parent = root.val;
if (root.left != null) {
int leftChild = root.left.val;
if (!map.containsKey(parent)) {
map.put(parent, new ArrayList());
}
if (!map.containsKey(leftChild)) {
map.put(leftChild, new ArrayList());
}
map.get(parent).add(new int[]{leftChild, 0});
map.get(leftChild).add(new int[]{parent, 2});
}
if (root.right != null) {
int rightChild = root.right.val;
if (!map.containsKey(parent)) {
map.put(parent, new ArrayList());
}
if (!map.containsKey(rightChild)) {
map.put(rightChild, new ArrayList());
}
map.get(parent).add(new int[]{rightChild, 1});
map.get(rightChild).add(new int[]{parent, 2});
}
if (root.left != null) {
dfs(root.left, map);
}
if (root.right != null) {
dfs(root.right, map);
}
}
public static String bfs(TreeNode root, Map map, int startValue, int destValue) {
Queue queue = new LinkedList();
Map pathMap = new HashMap();
boolean visited[] = new boolean[map.size() + 1];
//add startNode's Neighbour
if (map.containsKey(startValue)) {
for (int[] arr : map.get(startValue)) {
queue.offer(arr);
if (arr[1] == 0) {
pathMap.put(arr[0], "L");
} else if (arr[1] == 1) {
pathMap.put(arr[0], "R");
} else {
pathMap.put(arr[0], "U");
}
}
}
visited[startValue] = true;
while (!queue.isEmpty()) {
int[] popped = queue.poll();
int node = popped[0];
int dir = popped[1];
if (!visited[node]) {
visited[node] = true;
// if we got the destination them return it
if (node == destValue) {
return pathMap.get(node);
}
if (map.containsKey(node)) {
for (int[] arr : map.get(node)) {
int u = arr[0];
if (!visited[u]) {
queue.offer(arr);
String newPath = pathMap.get(node) + (arr[1] == 0 ? "L" : arr[1] == 1 ? "R" : "U");
pathMap.put(u, newPath);
}
}
}
}
}
return "";
}
public static String getDirections(TreeNode root, int startValue, int destValue) {
// Create Graph from Tree
Map map = new HashMap();
dfs(root, map);
return bfs(root, map, startValue, destValue);
}
}
segment tree video please
"kth ancestor of a node" please explain this question
My navie approach in C++ :
class Solution {
public:
unordered_map mp;
TreeNode* start = NULL;
string ans = "";
void f(TreeNode* root, int startValue) {
if (!root)
return;
if (root->val == startValue) {
start = root;
}
if (root->left != NULL) {
mp[root->left] = root;
f(root->left, startValue);
}
if (root->right != NULL) {
mp[root->right] = root;
f(root->right, startValue);
}
}
void bfs(TreeNode* root, set s, int d, string temp) {
if (root->val == d) {
ans = temp;
return;
}
s.insert(root);
if (mp.find(root) != mp.end() && s.count(mp[root]) == 0) {
bfs(mp[root], s, d, temp + 'U');
}
if (root->left != NULL && s.count(root->left) == 0) {
bfs(root->left, s, d, temp + 'L');
}
if (root->right != NULL && s.count(root->right) == 0) {
bfs(root->right, s, d, temp + 'R');
}
}
string getDirections(TreeNode* root, int startValue, int destValue) {
f(root, startValue);
bfs(start, {}, destValue, "");
return ans;
}
};
thanks
nice
please make a video on 2 keys keyboard leetcode 650
my naive approach
class Solution {
public:
unordered_map parent;
TreeNode* startNode = nullptr;
string res_path = "";
void inorder(TreeNode* root, int startValue) {
if (root == nullptr) {
return;
}
if (root->val == startValue) {
startNode = root;
}
if (root->right != nullptr) {
parent[root->right] = root;
inorder(root->right, startValue);
}
if (root->left != nullptr) {
parent[root->left] = root;
inorder(root->left, startValue);
}
}
void solver(TreeNode* root, int destValue, string res, unordered_set& visited) {
if (root == nullptr) {
return;
}
if (visited.find(root) != visited.end()) {
return;
}
visited.insert(root);
if (root->val == destValue) {
if (res_path.empty() || res.size() < res_path.size()) {
res_path = res;
}
return;
}
if (root->left) {
solver(root->left, destValue, res + 'L', visited);
}
if (root->right) {
solver(root->right, destValue, res + 'R', visited);
}
if (parent[root]) {
solver(parent[root], destValue, res + 'U', visited);
}
visited.erase(root);
}
string getDirections(TreeNode* root, int startValue, int destValue) {
inorder(root, startValue);
parent[root] = nullptr;
unordered_set visited;
solver(startNode, destValue, "", visited);
return res_path;
}
};
//Implementing the naive approach shows a Memory Limit Exceed WARNING!!
string getDirections(TreeNode* root, int startValue, int destValue) {
// populating parent-node
queue q;
unordered_map parent;
TreeNode* startNode = NULL;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
if (node->val == startValue) startNode = node;
q.pop();
if (node->left != NULL) {
parent[node->left->val] = node;
q.push(node->left);
}
if (node->right != NULL) {
parent[node->right->val] = node;
q.push(node->right);
}
}
if (startNode == NULL) return ""; // If startValue is not found in the tree
queue q2;
unordered_set visited;
q2.push({startNode, ""});
visited.insert(startNode->val);
while (!q2.empty()) {
TreeNode* node = q2.front().first;
string ret = q2.front().second;
q2.pop();
if (node->val == destValue) return ret;
if (parent.count(node->val) && !visited.count(parent[node->val]->val)) {
q2.push({parent[node->val], ret + 'U'});
visited.insert(parent[node->val]->val);
}
if (node->left != NULL && !visited.count(node->left->val)) {
q2.push({node->left, ret + 'L'});
visited.insert(node->left->val);
}
if (node->right != NULL && !visited.count(node->right->val)) {
q2.push({node->right, ret + 'R'});
visited.insert(node->right->val);
}
}
return "";
}
please help me with the naive approach
my graph and trees are very weak :(
implementing bfs approach solved 287 testcases and for rest got memory limit exceeded
class Solution {
public:
void updatemap(TreeNode* root,unordered_map &mp){
if(root==NULL) return;
if(root->left) mp[root->left]=root;
if(root->right) mp[root->right]=root;
updatemap(root->left,mp);
updatemap(root->right,mp);
}
TreeNode* findstart(TreeNode* root, int startValue) {
if (root == NULL) return NULL;
if (root->val == startValue) return root;
TreeNode* leftResult = findstart(root->left, startValue);
if (leftResult != NULL) {
return leftResult;
}
TreeNode* rightResult = findstart(root->right, startValue);
return rightResult;
}
string findans(TreeNode* start, TreeNode* target, unordered_map& parent_map) {
// BFS to find the shortest path from start to target
unordered_map visited;
unordered_map path_to_root;
queue q;
q.push(start);
visited[start] = true;
path_to_root[start] = "";
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node == target) break;
if (node->left && !visited[node->left]) {
visited[node->left] = true;
path_to_root[node->left] = path_to_root[node] + "L";
q.push(node->left);
}
if (node->right && !visited[node->right]) {
visited[node->right] = true;
path_to_root[node->right] = path_to_root[node] + "R";
q.push(node->right);
}
if (parent_map[node] && !visited[parent_map[node]]) {
visited[parent_map[node]] = true;
path_to_root[parent_map[node]] = path_to_root[node] + "U";
q.push(parent_map[node]);
}
}
return path_to_root[target];
}
string getDirections(TreeNode* root, int startValue, int destValue) {
unordered_map parent_map;
updatemap(root, parent_map);
TreeNode* start = findstart(root, startValue);
TreeNode* target = findstart(root, destValue);
return findans(start, target, parent_map);
}
};
Should be marked as hard
hello sir i need help : spending so much time on single question
i want to say that curruntly i am at Arrays & bs and sorting algo and i am taking too much time on single medium level q. where as i can apply brute force on some questoin but i take too much time even though i know concept very well is i am trying too perfect to solve question ???!!! bcz i calculated whn i am learning book allocation problem i took 7-8 hours to understand and dry run 2 example and then only i feel confident on any topic !! what is solution for this i have 2 months for preparing please help sir !!
for(int i = l; i < rootToDst.length(); i++) {
result.push_back(rootToDst[i]);
} bhaiya is wale loop me I = l se kyu chalega batyega bhaiya please
Sir, can you tell me please what's your tablet name is?
Ipad 11 pro
bfs mene kabhi kia nai only linear data structures.. kaha seekhu?
Why is the source always on the left and the destination always on the right? Why can't the vice-versa be possible?
You're replacing LCAToSrc by "UU". This is irrespective of whether the source is on the left or right.
hii sir, this is my lowest common ancestor code , a little diffrent from yours but same logic but idk why in a perticular case the common head parent node is wrong can you explain
TreeNode*lca(TreeNode* root, int s, int d)
{
if(!root) return NULL;
if(root->val == s || root->val ==d) return root;
TreeNode*leftans = lca(root->left,s,d);
TreeNode*rightans = lca(root->right,s,d);
if(leftans!=NULL &&& rightans!=NULL)
{
return root;
}
if(leftans==NULL &&& rightans!=NULL)
{
return rightans;
}
if(leftans!=NULL &&& rightans==NULL)
{
return leftans;
}
else return NULL;
}
khud hi smaj aa gyaa , mai "&&" iske place pe "&&&"
ye likh diya
Cool 🙌❤️
My Lowest common ancestor solution
TreeNode* findLca(TreeNode* root, int p, int q) {
if (root == NULL || root->val == p || root->val == q) {
return root;
}
TreeNode* left = findLca(root->left, p, q);
TreeNode* right = findLca(root->right, p, q);
if (left == NULL) {
return right;
}
if (right == NULL) {
return left;
}
return root;
}
string getDirections(TreeNode* root, int st, int ed) {
unordered_map parentMap;
TreeNode* start = nullptr;
TreeNode* end = nullptr;
queue q;
q.push(root);
parentMap[root] = nullptr;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node->val == st) start = node;
if (node->val == ed) end = node;
if (node->left) {
parentMap[node->left] = node;
q.push(node->left);
}
if (node->right) {
parentMap[node->right] = node;
q.push(node->right);
}
}
TreeNode* lca = findLca(root, st, ed);
string pathToStart = "";
string pathToEnd = "";
while (start != lca) {
pathToStart.push_back('U');
start = parentMap[start];
}
while (end != lca) {
if (parentMap[end]->left == end) {
pathToEnd.push_back('L');
} else {
pathToEnd.push_back('R');
}
end = parentMap[end];
}
reverse(pathToEnd.begin(),pathToEnd.end());
return pathToStart + pathToEnd;
}
Guys graph approach is failing Memory limit exceeded
Bhaiya LC:2055 plates between candles plz , Segment Trees lg skta h kya isme?
it is not easy 😢
haa hard hai
yaar mae bfs bhul gaya😵💫