Tree
Depth-First Search
String
Binary Tree
Description
You are given the root
of a binary tree with n
nodes. Each node is uniquely assigned a value from 1
to n
. You are also given an integer startValue
representing the value of the start node s
, and a different integer destValue
representing the value of the destination node t
.
Find the shortest path starting from node s
and ending at node t
. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L'
, 'R'
, and 'U'
. Each letter indicates a specific direction:
'L'
means to go from a node to its left child node.
'R'
means to go from a node to its right child node.
'U'
means to go from a node to its parent node.
Return the step-by-step directions of the shortest path from node s
to node t
.
Example 1:
Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.
Example 2:
Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.
Constraints:
The number of nodes in the tree is n
.
2 <= n <= 105
1 <= Node.val <= n
All the values in the tree are unique .
1 <= startValue, destValue <= n
startValue != destValue
Solutions
Solution 1: Lowest Common Ancestor + DFS
We can first find the lowest common ancestor of nodes $\textit{startValue}$ and $\textit{destValue}$, denoted as $\textit{node}$. Then, starting from $\textit{node}$, we find the paths to $\textit{startValue}$ and $\textit{destValue}$ respectively. The path from $\textit{startValue}$ to $\textit{node}$ will consist of a number of $\textit{U}$s, and the path from $\textit{node}$ to $\textit{destValue}$ will be the $\textit{path}$. Finally, we concatenate these two paths.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def getDirections (
self , root : Optional [ TreeNode ], startValue : int , destValue : int
) -> str :
def lca ( node : Optional [ TreeNode ], p : int , q : int ):
if node is None or node . val in ( p , q ):
return node
left = lca ( node . left , p , q )
right = lca ( node . right , p , q )
if left and right :
return node
return left or right
def dfs ( node : Optional [ TreeNode ], x : int , path : List [ str ]):
if node is None :
return False
if node . val == x :
return True
path . append ( "L" )
if dfs ( node . left , x , path ):
return True
path [ - 1 ] = "R"
if dfs ( node . right , x , path ):
return True
path . pop ()
return False
node = lca ( root , startValue , destValue )
path_to_start = []
path_to_dest = []
dfs ( node , startValue , path_to_start )
dfs ( node , destValue , path_to_dest )
return "U" * len ( path_to_start ) + "" . join ( path_to_dest )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 class Solution {
public String getDirections ( TreeNode root , int startValue , int destValue ) {
TreeNode node = lca ( root , startValue , destValue );
StringBuilder pathToStart = new StringBuilder ();
StringBuilder pathToDest = new StringBuilder ();
dfs ( node , startValue , pathToStart );
dfs ( node , destValue , pathToDest );
return "U" . repeat ( pathToStart . length ()) + pathToDest . toString ();
}
private TreeNode lca ( TreeNode node , int p , int q ) {
if ( node == null || node . val == p || node . val == q ) {
return node ;
}
TreeNode left = lca ( node . left , p , q );
TreeNode right = lca ( node . right , p , q );
if ( left != null && right != null ) {
return node ;
}
return left != null ? left : right ;
}
private boolean dfs ( TreeNode node , int x , StringBuilder path ) {
if ( node == null ) {
return false ;
}
if ( node . val == x ) {
return true ;
}
path . append ( 'L' );
if ( dfs ( node . left , x , path )) {
return true ;
}
path . setCharAt ( path . length () - 1 , 'R' );
if ( dfs ( node . right , x , path )) {
return true ;
}
path . deleteCharAt ( path . length () - 1 );
return false ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 /**
* 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 :
string getDirections ( TreeNode * root , int startValue , int destValue ) {
TreeNode * node = lca ( root , startValue , destValue );
string pathToStart , pathToDest ;
dfs ( node , startValue , pathToStart );
dfs ( node , destValue , pathToDest );
return string ( pathToStart . size (), 'U' ) + pathToDest ;
}
private :
TreeNode * lca ( TreeNode * node , int p , int q ) {
if ( node == nullptr || node -> val == p || node -> val == q ) {
return node ;
}
TreeNode * left = lca ( node -> left , p , q );
TreeNode * right = lca ( node -> right , p , q );
if ( left != nullptr && right != nullptr ) {
return node ;
}
return left != nullptr ? left : right ;
}
bool dfs ( TreeNode * node , int x , string & path ) {
if ( node == nullptr ) {
return false ;
}
if ( node -> val == x ) {
return true ;
}
path . push_back ( 'L' );
if ( dfs ( node -> left , x , path )) {
return true ;
}
path . back () = 'R' ;
if ( dfs ( node -> right , x , path )) {
return true ;
}
path . pop_back ();
return false ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getDirections ( root * TreeNode , startValue int , destValue int ) string {
var lca func ( node * TreeNode , p , q int ) * TreeNode
lca = func ( node * TreeNode , p , q int ) * TreeNode {
if node == nil || node . Val == p || node . Val == q {
return node
}
left := lca ( node . Left , p , q )
right := lca ( node . Right , p , q )
if left != nil && right != nil {
return node
}
if left != nil {
return left
}
return right
}
var dfs func ( node * TreeNode , x int , path * [] byte ) bool
dfs = func ( node * TreeNode , x int , path * [] byte ) bool {
if node == nil {
return false
}
if node . Val == x {
return true
}
* path = append ( * path , 'L' )
if dfs ( node . Left , x , path ) {
return true
}
( * path )[ len ( * path ) - 1 ] = 'R'
if dfs ( node . Right , x , path ) {
return true
}
* path = ( * path )[: len ( * path ) - 1 ]
return false
}
node := lca ( root , startValue , destValue )
pathToStart := [] byte {}
pathToDest := [] byte {}
dfs ( node , startValue , & pathToStart )
dfs ( node , destValue , & pathToDest )
return string ( bytes . Repeat ([] byte { 'U' }, len ( pathToStart ))) + string ( pathToDest )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getDirections ( root : TreeNode | null , startValue : number , destValue : number ) : string {
const lca = ( node : TreeNode | null , p : number , q : number ) : TreeNode | null => {
if ( node === null || [ p , q ]. includes ( node . val )) {
return node ;
}
const left = lca ( node . left , p , q );
const right = lca ( node . right , p , q );
return left && right ? node : left ?? right ;
};
const dfs = ( node : TreeNode | null , x : number , path : string []) : boolean => {
if ( node === null ) {
return false ;
}
if ( node . val === x ) {
return true ;
}
path . push ( 'L' );
if ( dfs ( node . left , x , path )) {
return true ;
}
path [ path . length - 1 ] = 'R' ;
if ( dfs ( node . right , x , path )) {
return true ;
}
path . pop ();
return false ;
};
const node = lca ( root , startValue , destValue );
const pathToStart : string [] = [];
const pathToDest : string [] = [];
dfs ( node , startValue , pathToStart );
dfs ( node , destValue , pathToDest );
return 'U' . repeat ( pathToStart . length ) + pathToDest . join ( '' );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 /**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} startValue
* @param {number} destValue
* @return {string}
*/
var getDirections = function ( root , startValue , destValue ) {
const lca = ( node , p , q ) => {
if ( node === null || [ p , q ]. includes ( node . val )) {
return node ;
}
const left = lca ( node . left , p , q );
const right = lca ( node . right , p , q );
return left && right ? node : left ?? right ;
};
const dfs = ( node , x , path ) => {
if ( node === null ) {
return false ;
}
if ( node . val === x ) {
return true ;
}
path . push ( 'L' );
if ( dfs ( node . left , x , path )) {
return true ;
}
path [ path . length - 1 ] = 'R' ;
if ( dfs ( node . right , x , path )) {
return true ;
}
path . pop ();
return false ;
};
const node = lca ( root , startValue , destValue );
const pathToStart = [];
const pathToDest = [];
dfs ( node , startValue , pathToStart );
dfs ( node , destValue , pathToDest );
return 'U' . repeat ( pathToStart . length ) + pathToDest . join ( '' );
};
Solution 2: Lowest Common Ancestor + DFS (Optimized)
We can start from $\textit{root}$, find the paths to $\textit{startValue}$ and $\textit{destValue}$, denoted as $\textit{pathToStart}$ and $\textit{pathToDest}$, respectively. Then, remove the longest common prefix of $\textit{pathToStart}$ and $\textit{pathToDest}$. At this point, the length of $\textit{pathToStart}$ is the number of $\textit{U}$s in the answer, and the path of $\textit{pathToDest}$ is the path in the answer. We just need to concatenate these two paths.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def getDirections (
self , root : Optional [ TreeNode ], startValue : int , destValue : int
) -> str :
def dfs ( node : Optional [ TreeNode ], x : int , path : List [ str ]):
if node is None :
return False
if node . val == x :
return True
path . append ( "L" )
if dfs ( node . left , x , path ):
return True
path [ - 1 ] = "R"
if dfs ( node . right , x , path ):
return True
path . pop ()
return False
path_to_start = []
path_to_dest = []
dfs ( root , startValue , path_to_start )
dfs ( root , destValue , path_to_dest )
i = 0
while (
i < len ( path_to_start )
and i < len ( path_to_dest )
and path_to_start [ i ] == path_to_dest [ i ]
):
i += 1
return "U" * ( len ( path_to_start ) - i ) + "" . join ( path_to_dest [ i :])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 class Solution {
public String getDirections ( TreeNode root , int startValue , int destValue ) {
StringBuilder pathToStart = new StringBuilder ();
StringBuilder pathToDest = new StringBuilder ();
dfs ( root , startValue , pathToStart );
dfs ( root , destValue , pathToDest );
int i = 0 ;
while ( i < pathToStart . length () && i < pathToDest . length ()
&& pathToStart . charAt ( i ) == pathToDest . charAt ( i )) {
++ i ;
}
return "U" . repeat ( pathToStart . length () - i ) + pathToDest . substring ( i );
}
private boolean dfs ( TreeNode node , int x , StringBuilder path ) {
if ( node == null ) {
return false ;
}
if ( node . val == x ) {
return true ;
}
path . append ( 'L' );
if ( dfs ( node . left , x , path )) {
return true ;
}
path . setCharAt ( path . length () - 1 , 'R' );
if ( dfs ( node . right , x , path )) {
return true ;
}
path . deleteCharAt ( path . length () - 1 );
return false ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 /**
* 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 :
string getDirections ( TreeNode * root , int startValue , int destValue ) {
string pathToStart , pathToDest ;
dfs ( root , startValue , pathToStart );
dfs ( root , destValue , pathToDest );
int i = 0 ;
while ( i < pathToStart . size () && i < pathToDest . size () && pathToStart [ i ] == pathToDest [ i ]) {
i ++ ;
}
return string ( pathToStart . size () - i , 'U' ) + pathToDest . substr ( i );
}
private :
bool dfs ( TreeNode * node , int x , string & path ) {
if ( node == nullptr ) {
return false ;
}
if ( node -> val == x ) {
return true ;
}
path . push_back ( 'L' );
if ( dfs ( node -> left , x , path )) {
return true ;
}
path . back () = 'R' ;
if ( dfs ( node -> right , x , path )) {
return true ;
}
path . pop_back ();
return false ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getDirections ( root * TreeNode , startValue int , destValue int ) string {
var dfs func ( node * TreeNode , x int , path * [] byte ) bool
dfs = func ( node * TreeNode , x int , path * [] byte ) bool {
if node == nil {
return false
}
if node . Val == x {
return true
}
* path = append ( * path , 'L' )
if dfs ( node . Left , x , path ) {
return true
}
( * path )[ len ( * path ) - 1 ] = 'R'
if dfs ( node . Right , x , path ) {
return true
}
* path = ( * path )[: len ( * path ) - 1 ]
return false
}
pathToStart := [] byte {}
pathToDest := [] byte {}
dfs ( root , startValue , & pathToStart )
dfs ( root , destValue , & pathToDest )
i := 0
for i < len ( pathToStart ) && i < len ( pathToDest ) && pathToStart [ i ] == pathToDest [ i ] {
i ++
}
return string ( bytes . Repeat ([] byte { 'U' }, len ( pathToStart ) - i )) + string ( pathToDest [ i :])
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getDirections ( root : TreeNode | null , startValue : number , destValue : number ) : string {
const dfs = ( node : TreeNode | null , x : number , path : string []) : boolean => {
if ( node === null ) {
return false ;
}
if ( node . val === x ) {
return true ;
}
path . push ( 'L' );
if ( dfs ( node . left , x , path )) {
return true ;
}
path [ path . length - 1 ] = 'R' ;
if ( dfs ( node . right , x , path )) {
return true ;
}
path . pop ();
return false ;
};
const pathToStart : string [] = [];
const pathToDest : string [] = [];
dfs ( root , startValue , pathToStart );
dfs ( root , destValue , pathToDest );
let i = 0 ;
while ( pathToStart [ i ] === pathToDest [ i ]) {
++ i ;
}
return 'U' . repeat ( pathToStart . length - i ) + pathToDest . slice ( i ). join ( '' );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 /**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} startValue
* @param {number} destValue
* @return {string}
*/
var getDirections = function ( root , startValue , destValue ) {
const dfs = ( node , x , path ) => {
if ( node === null ) {
return false ;
}
if ( node . val === x ) {
return true ;
}
path . push ( 'L' );
if ( dfs ( node . left , x , path )) {
return true ;
}
path [ path . length - 1 ] = 'R' ;
if ( dfs ( node . right , x , path )) {
return true ;
}
path . pop ();
return false ;
};
const pathToStart = [];
const pathToDest = [];
dfs ( root , startValue , pathToStart );
dfs ( root , destValue , pathToDest );
let i = 0 ;
while ( pathToStart [ i ] === pathToDest [ i ]) {
++ i ;
}
return 'U' . repeat ( pathToStart . length - i ) + pathToDest . slice ( i ). join ( '' );
};