Given a root of binary tree and two integers startValue and destValue denoting the starting and ending node respectively. The task is to find the shortest path from the start node to the end node and print the path in the form of directions given below.
- Going from one node to its left child node is indicated by the letter ‘L’.
- Going from one node to its right child node is indicated by the letter ‘R’.
- To navigate from a node to its parent node, use the letter ‘U’.
Examples:
Input: root = [5, 1, 2, 3, null, 6, 4], startValue = 3, destValue = 6
5
/ \
1 2
/ / \
3 6 4Output: “UURL”
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.Input: root = [2, 1], startValue = 2, destValue = 1
2
/
1Output: “L”
Explanation: The shortest path is: 2 → 1.
Approach: The simplest way to solve this problem is to use the LCA (Lowest Common Ancestor) of a binary tree. Follow the steps below to solve the given problem.
- Apply LCA to get a new root.
- Get the Path from the new root to start and dest.
- Concatenate startPath and destPath, and make sure to replace startPath’s char with ‘U’.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <iostream>using namespace std;// Structure of Treeclass TreeNode {public: int val; TreeNode* left; TreeNode* right; TreeNode(int val2) { val = val2; left = NULL; right = NULL; }};// Function to find LCA of two nodesTreeNode* lca(TreeNode* root, int startValue, int destValue){ // Base Case if (!root) return NULL; if (root->val == startValue) return root; if (root->val == destValue) return root; auto l = lca(root->left, startValue, destValue); auto r = lca(root->right, startValue, destValue); if (l && r) return root; return l ? l : r;}bool getPath(TreeNode* root, int value, string& path){ // Base Cases if (!root) return false; if (root->val == value) return true; path += 'L'; auto res = getPath(root->left, value, path); if (res) return true; path.pop_back(); path += 'R'; res = getPath(root->right, value, path); if (res) return true; path.pop_back(); return false;}// Function to get directionsstring getDirections(TreeNode* root, int startValue, int destValue){ // Find the LCA first root = lca(root, startValue, destValue); string p1, p2; // Get the path getPath(root, startValue, p1); getPath(root, destValue, p2); for (auto& c : p1) c = 'U'; // Return the concatenation return p1 + p2;}// Driver Codeint main(){ /* 5 / \ 1 2 / / \ 3 6 4 */ TreeNode* root = new TreeNode(5); root->left = new TreeNode(1); root->right = new TreeNode(2); root->left->left = new TreeNode(3); root->right->left = new TreeNode(6); root->right->right = new TreeNode(4); int startValue = 3; int endValue = 6; // Function Call string ans = getDirections( root, startValue, endValue); // Print answer cout << ans;} |
Java
// Java program for above approachclass TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; left = null; right = null; }}// Function to find LCA of two nodesclass Solution { TreeNode lca(TreeNode root, int startValue, int destValue) { // Base Case if (root == null) { return null; } if (root.val == startValue) { return root; } if (root.val == destValue) { return root; } TreeNode l = lca(root.left, startValue, destValue); TreeNode r = lca(root.right, startValue, destValue); if (l != null && r != null) { return root; } return l != null ? l : r; } boolean getPath(TreeNode root, int value, StringBuilder path) { // Base Cases if (root == null) { return false; } if (root.val == value) { return true; } path.append("L"); boolean res = getPath(root.left, value, path); if (res) { return true; } path.deleteCharAt(path.length() - 1); path.append("R"); res = getPath(root.right, value, path); if (res) { return true; } path.deleteCharAt(path.length() - 1); return false; } // Function to get directions String getDirections(TreeNode root, int startValue, int destValue) { // Find the LCA first root = lca(root, startValue, destValue); StringBuilder p1 = new StringBuilder(); StringBuilder p2 = new StringBuilder(); // Get the path getPath(root, startValue, p1); getPath(root, destValue, p2); for (int i = 0; i < p1.length(); i++) { p1.setCharAt(i, 'U'); } // Return the concatenation return p1.append(p2).toString(); }}// Driver Codepublic class Main { public static void main(String[] args) { /* 5 / \ 1 2 / / \ 3 6 4 */ TreeNode root = new TreeNode(5); root.left = new TreeNode(1); root.right = new TreeNode(2); root.left.left = new TreeNode(3); root.right.left = new TreeNode(6); root.right.right = new TreeNode(4); int startValue = 3; int endValue = 6; // Function Call Solution solution = new Solution(); String ans = solution.getDirections( root, startValue, endValue); // Print answer System.out.println(ans); }} |
Python3
# Python program for above approach # Structure of Treeclass TreeNode : def __init__(self, val2): self.val = val2; self.left = None; self.right = None;# Function to find LCA of two nodesdef lca(root, startValue, destValue): # Base Case if (not root): return None; if (root.val == startValue): return root; if (root.val == destValue): return root; l = lca(root.left, startValue, destValue); r = lca(root.right, startValue, destValue); if (l and r): return root; return l if l else r;def getPath(root, value, path) : # Base Cases if (not root): return False; if (root.val == value): return True; path.append('L'); res = getPath(root.left, value, path); if (res): return True; path.pop(); path.append('R'); res = getPath(root.right, value, path); if (res): return True; path.pop(); return False;# Function to get directionsdef getDirections(root, startValue, destValue) : # Find the LCA first root = lca(root, startValue, destValue); p1 = [] p2 = [] # Get the path getPath(root, startValue, p1); getPath(root, destValue, p2); for i in range(len(p1)): p1[i] = 'U'; # Return the concatenation s = "" for i in range(len(p1)): s += p1[i]; for i in range(len(p2)): s += p2[i]; return s;# Driver Code""" 5 / \ 1 2 / / \ 3 6 4"""root = TreeNode(5);root.left = TreeNode(1);root.right = TreeNode(2);root.left.left = TreeNode(3);root.right.left = TreeNode(6);root.right.right = TreeNode(4);startValue = 3;endValue = 6;# Function Callans = getDirections(root, startValue, endValue);# Print answerprint(ans)# self code is contributed by Saurabh Jaiswal |
C#
using System;using System.Text;class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; left = null; right = null; }}class Solution{ public TreeNode lca(TreeNode root, int startValue, int destValue) { // Base Case if (root == null) { return null; } if (root.val == startValue) { return root; } if (root.val == destValue) { return root; } TreeNode l = lca(root.left, startValue, destValue); TreeNode r = lca(root.right, startValue, destValue); if (l != null && r != null) { return root; } return l != null ? l : r; } public bool getPath(TreeNode root, int value, StringBuilder path) { // Base Cases if (root == null) { return false; } if (root.val == value) { return true; } path.Append("L"); bool res = getPath(root.left, value, path); if (res) { return true; } path.Remove(path.Length - 1, 1); path.Append("R"); res = getPath(root.right, value, path); if (res) { return true; } path.Remove(path.Length - 1, 1); return false; } public string getDirections(TreeNode root, int startValue, int destValue) { // Find the LCA first root = lca(root, startValue, destValue); StringBuilder p1 = new StringBuilder(); StringBuilder p2 = new StringBuilder(); // Get the path getPath(root, startValue, p1); getPath(root, destValue, p2); for (int i = 0; i < p1.Length; i++) { p1[i] = 'U'; } // Return the concatenation return p1.Append(p2).ToString(); }}public class Program{ public static void Main(string[] args) { /* 5 / \ 1 2 / / \ 3 6 4 */ TreeNode root = new TreeNode(5); root.left = new TreeNode(1); root.right = new TreeNode(2); root.left.left = new TreeNode(3); root.right.left = new TreeNode(6); root.right.right = new TreeNode(4); int startValue = 3; int endValue = 6; // Function Call Solution solution = new Solution(); string ans = solution.getDirections(root, startValue, endValue); // Print answer Console.WriteLine(ans); }} |
Javascript
<script>// JavaScript program for above approach // Structure of Treeclass TreeNode { constructor(val2) { this.val = val2; this.left = null; this.right = null; }};// Function to find LCA of two nodesfunction lca(root, startValue, destValue){ // Base Case if (!root) return null; if (root.val == startValue) return root; if (root.val == destValue) return root; let l = lca(root.left, startValue, destValue); let r = lca(root.right, startValue, destValue); if (l && r) return root; return l ? l : r;}function getPath(root, value, path) { // Base Cases if (!root) return false; if (root.val == value) return true; path.push('L'); let res = getPath(root.left, value, path); if (res) return true; path.pop(); path.push('R'); res = getPath(root.right, value, path); if (res) return true; path.pop(); return false;}// Function to get directionsfunction getDirections(root, startValue, destValue) { // Find the LCA first root = lca(root, startValue, destValue); let p1 = [], p2 = []; // Get the path getPath(root, startValue, p1); getPath(root, destValue, p2); for(let i = 0; i < p1.length; i++) p1[i] = 'U'; // Return the concatenation let s = "" for(let i = 0; i < p1.length; i++) { s += p1[i]; } for(let i = 0; i < p2.length; i++) { s += p2[i]; } return s;}// Driver Code/* 5 / \ 1 2 / / \ 3 6 4*/let root = new TreeNode(5);root.left = new TreeNode(1);root.right = new TreeNode(2);root.left.left = new TreeNode(3);root.right.left = new TreeNode(6);root.right.right = new TreeNode(4);let startValue = 3;let endValue = 6;// Function Calllet ans = getDirections(root, startValue, endValue);// Print answerdocument.write(ans)// This code is contributed by Potta Lokesh</script> |
Output
UURL
Time complexity: O(3N), Because three traversals are done.
Auxiliary Space: O(N)
Efficient Approach: This approach is implementation based but LCA is not used in this approach. Follow the steps below to solve the given problem.
- Build directions for both start and destination from the root.
- Say we get “LLRRL” and “LRR”.
- Remove common prefix path.
- We remove “L”, and now start direction is “LRRL”, and destination – “RR”
- Replace all steps in the start direction to “U” and add the destination direction.
- The result is “UUUU” + “RR”.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Structure of Treeclass TreeNode {public: int val; TreeNode* left; TreeNode* right; TreeNode(int val2) { val = val2; left = NULL; right = NULL; }};// Find Functionbool find(TreeNode* n, int val, string& path){ if (n->val == val) return true; if (n->left && find(n->left, val, path)) { path.push_back('L'); return true; } if (n->right && find(n->right, val, path)) { path.push_back('R'); return true; } return false;}// Function to keep track // of directions at any pointstring getDirections(TreeNode* root, int startValue, int destValue){ // To store the startPath and destPath string s_p, d_p; find(root, startValue, s_p); find(root, destValue, d_p); while (!s_p.empty() && !d_p.empty() && s_p.back() == d_p.back()) { s_p.pop_back(); d_p.pop_back(); } for (int i = 0; i < s_p.size(); i++) { s_p[i] = 'U'; } reverse(d_p.begin(), d_p.end()); string ans = s_p + d_p; return ans;}// Driver Codeint main(){ /* 5 / \ 1 2 / / \ 3 6 4 */ TreeNode* root = new TreeNode(5); root->left = new TreeNode(1); root->right = new TreeNode(2); root->left->left = new TreeNode(3); root->right->left = new TreeNode(6); root->right->right = new TreeNode(4); int startValue = 3; int endValue = 6; // Function Call string ans = getDirections( root, startValue, endValue); // Print the result cout << ans;} |
Java
// Java Codeimport java.util.ArrayList;class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val2) { this.val = val2; this.left = null; this.right = null; }}class solution { // Find Function public static boolean find(TreeNode n, int val, ArrayList<String> path) { if (n.val == val) { return true; } if (n.left != null && find(n.left, val, path)) { path.add("R"); return true; } if (n.right != null && find(n.right, val, path)) { path.add("L"); return true; } return false; } // Function to keep track of directions at any point public static ArrayList<String> getDirections(TreeNode root, int startValue, int destValue) { // To store the startPath and destPath ArrayList<String> s_p = new ArrayList<>(); ArrayList<String> d_p = new ArrayList<>(); find(root, startValue, s_p); find(root, destValue, d_p); while (s_p.size() > 0 && d_p.size() > 0 && s_p.get(s_p.size() - 1) .equals(d_p.get(d_p.size() - 1))) { s_p.remove(s_p.size() - 1); d_p.remove(d_p.size() - 1); } for (int i = 0; i < s_p.size(); i++) { s_p.set(i, "U"); } //Collections.reverse(d_p); ArrayList<String> ans = new ArrayList<>(s_p); ans.addAll(d_p); return ans; } public static void main(String[] args) { TreeNode root = new TreeNode(5); root.left = new TreeNode(1); root.right = new TreeNode(2); root.left.left = new TreeNode(3); root.right.left = new TreeNode(6); root.right.right = new TreeNode(4); int startValue = 3; int endValue = 6; ArrayList<String> ans = getDirections(root, startValue, endValue); System.out.println(ans); }} |
Python
# Python program for above approachclass TreeNode: def __init__(self, val2): self.val = val2 self.left = None self.right = None# Find Functiondef find(n, val, path): if n.val == val: return True if n.left and find(n.left, val, path): path.append('L') return True if n.right and find(n.right, val, path): path.append('R') return True return False# Function to keep track # of directions at any pointdef getDirections(root, startValue, destValue): # To store the startPath and destPath s_p, d_p = [], [] find(root, startValue, s_p) find(root, destValue, d_p) while s_p and d_p and s_p[-1] == d_p[-1]: s_p.pop() d_p.pop() for i in range(len(s_p)): s_p[i] = 'U' d_p.reverse() ans = s_p + d_p return ansif __name__ == '__main__': root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(2) root.left.left = TreeNode(3) root.right.left = TreeNode(6) root.right.right = TreeNode(4) startValue = 3 endValue = 6 ans = getDirections(root, startValue, endValue) print(ans) # This code is contributed by aadityamaharshi21. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val2) { this.val = val2; this.left = null; this.right = null; }}public class GFG { // Find function static bool Find(TreeNode n, int val, List<string> path) { if (n.val == val) { return true; } if (n.left != null && Find(n.left, val, path)) { path.Add("R"); return true; } if (n.right != null && Find(n.right, val, path)) { path.Add("L"); return true; } return false; } // Function to keep track of directions at any point static List<string> GetDirections(TreeNode root, int startValue, int destValue) { // To store the startPath and destPath var s_p = new List<string>(); var d_p = new List<string>(); Find(root, startValue, s_p); Find(root, destValue, d_p); while (s_p.Count > 0 && d_p.Count > 0 && s_p[s_p.Count - 1] == d_p[d_p.Count - 1]) { s_p.RemoveAt(s_p.Count - 1); d_p.RemoveAt(d_p.Count - 1); } for (int i = 0; i < s_p.Count; i++) { s_p[i] = "U"; } // Collections.reverse(d_p) var ans = new List<string>(s_p); ans.AddRange(d_p); return ans; } static public void Main() { // Code TreeNode root = new TreeNode(5); root.left = new TreeNode(1); root.right = new TreeNode(2); root.left.left = new TreeNode(3); root.right.left = new TreeNode(6); root.right.right = new TreeNode(4); int startValue = 3; int endValue = 6; var ans = GetDirections(root, startValue, endValue); Console.WriteLine(string.Join("", ans)); }}// This code is contributed by karthik. |
Javascript
// JavaScript Codeclass TreeNode { constructor(val2) { this.val = val2; this.left = null; this.right = null; }}// Find Functionfunction find(n, val, path) { if (n.val === val) { return true; } if (n.left && find(n.left, val, path)) { path.push("L"); return true; } if (n.right && find(n.right, val, path)) { path.push("R"); return true; } return false;}// Function to keep track of directions at any pointfunction getDirections(root, startValue, destValue) { // To store the startPath and destPath let s_p = [], d_p = []; find(root, startValue, s_p); find(root, destValue, d_p); while (s_p.length && d_p.length && s_p[s_p.length - 1] === d_p[d_p.length - 1]) { s_p.pop(); d_p.pop(); } for (let i = 0; i < s_p.length; i++) { s_p[i] = "U"; } d_p.reverse(); let ans = s_p.concat(d_p); return ans;}let root = new TreeNode(5);root.left = new TreeNode(1);root.right = new TreeNode(2);root.left.left = new TreeNode(3);root.right.left = new TreeNode(6);root.right.right = new TreeNode(4);let startValue = 3;let endValue = 6;let ans = getDirections(root, startValue, endValue);console.log(ans);// This code is contributed by vinayetbi1. |
Output
UURL
Time complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
