LeetCode2096: Step-By-Step Directions From a Binary Tree Node to Another

Abhinay Gupta
1 min readOct 11, 2022

--

Algorithm: Find the Strings from root to start and root to dest. And then remove the common prefix of both the strings. Replace each character of start string with ‘U’ . And concatinate the start string with the reversed dest string.

/**
* 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 {
StringBuilder path = new StringBuilder("");
public String getDirections(TreeNode root, int startValue, int destValue) {
getStringfromRootToNode(root, startValue);
StringBuilder start = path.reverse();
path=new StringBuilder("");
getStringfromRootToNode(root, destValue);
StringBuilder dest= path.reverse();
removeCommonPrefix(start,dest);
replaceStartString(start);
return concatinateStrings(start,dest);

}

public Boolean getStringfromRootToNode(TreeNode root , int value){
// return reverse strings from root to valueNode
if(root.val==value) return true;
if(root.left!=null && getStringfromRootToNode(root.left,value)) {
path.append("L");
return true;
}
if(root.right!=null && getStringfromRootToNode(root.right,value)) {
path.append("R");
return true;
}
return false;

}

public void removeCommonPrefix(StringBuilder s1, StringBuilder s2){
//remove common prefix
while(s1.length()!=0 && s2.length()!=0
&& s1.charAt(0)==s2.charAt(0)){
s1.deleteCharAt(0);
s2.deleteCharAt(0);

}
}

public void replaceStartString( StringBuilder s){
int i=0;
while(i<s.length()){
s.setCharAt(i,'U');
i++;
}
}


public String concatinateStrings(StringBuilder s1, StringBuilder s2){
//concatinate s1 with Us and reversed s2
s1.append(s2);
return s1.toString();
}

}

--

--