-
Notifications
You must be signed in to change notification settings - Fork 117
/
Binary Search Trees:Find Path in BST
58 lines (47 loc) · 1.26 KB
/
Binary Search Trees:Find Path in BST
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
54
55
56
57
58
import java.util.ArrayList;
public class Solution {
/* Binary Tree Node class
*
* class BinaryTreeNode<T> {
T data;
BinaryTreeNode<T> left;
BinaryTreeNode<T> right;
public BinaryTreeNode(T data) {
this.data = data;
}
}
*/
public static ArrayList<Integer> findPath(BinaryTreeNode<Integer> root, int data){
/* Your class should be named Solution
* Don't write main().
* Don't read input, it is passed as function argument.
* Return output and don't print it.
* Taking input and printing output is handled automatically.
*/
if(root==null)
return null;
if(root.data==data)
{
ArrayList<Integer> output=new ArrayList<>();
output.add(root.data);
return output;
}
if(data<root.data)
{
ArrayList<Integer> output=findPath(root.left,data);
if(output!=null)
{
output.add(root.data);
return output;
}
}
ArrayList<Integer> output2;
if(data>root.data)
{
output2=findPath(root.right,data);
if(output2!=null){
output2.add(root.data);
return output2;}}
return null;
}
}