-
Notifications
You must be signed in to change notification settings - Fork 0
/
BST2-Find path in BST
46 lines (39 loc) · 1.56 KB
/
BST2-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
Given a BST and an integer k. Find and return the path from the node with data k and root (if a node with data k is present in given BST) in a list. Return empty list otherwise.
Note: Assume that BST contains all unique elements.
Input Format :
The first line of input contains data of the nodes of the tree in level order form. The data of the nodes of the tree is separated by space. If any node does not have left or right child, take -1 in its place. Since -1 is used as an indication whether the left or right nodes exist, therefore, it will not be a part of the data of any node.
The following line of input contains an integer, that denotes the value of k.
Output Format :
The first line and only line of output prints the data of the nodes in the path from node k to root. The data of the nodes is separated by single space.
Constraints:
Time Limit: 1 second
Sample Input 1:
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
2
Sample Output 1:
2 5 8
********************************Solution************************************
import java.util.ArrayList;
public static ArrayList<Integer> getPath(BinaryTreeNode<Integer> root, int data){
if(root==null)
return null;
if(root.data==data)
{
ArrayList<Integer> ans=new ArrayList<Integer>();
ans.add(root.data);
return ans;
}
ArrayList<Integer> leftans= getPath(root.left, data);
if(leftans!=null)
{
leftans.add(root.data);
return leftans;
}
ArrayList<Integer> rightans= getPath(root.right, data);
if(rightans!=null)
{
rightans.add(root.data);
return rightans;
}
return null;
}