Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- class Node {
- int data;
- Node left, right;
- public Node(int item) {
- data = item;
- left = right = null;
- }
- }
- class BinarySearchTree {
- Node constructBST(int[] arr, int start, int end, Node root) {
- if (start > end)
- return null;
- int mid = (start + end) / 2;
- if (root == null)
- root = new Node(arr[mid]);
- root.left = constructBST(arr, start, mid - 1, root.left);
- root.right = constructBST(arr, mid + 1, end, root.right);
- return root;
- }
- }
- public class Main {
- public static void main(String[] args) throws Throwable {
- Scanner sc = new Scanner(System.in);
- int n = sc.nextInt();
- int arr[] = new int[n];
- for (int i = 0; i < n; i++) {
- arr[i] = sc.nextInt();
- }
- int target = sc.nextInt();
- Arrays.sort(arr);
- Node root = null;
- BinarySearchTree bst = new BinarySearchTree();
- root = bst.constructBST(arr, 0, n - 1, root);
- Accio A = new Accio();
- A.targetSum(root, target);
- sc.close();
- }
- }
- class Accio {
- boolean t=false;
- public boolean find(Node node, int data) {
- if (node == null) {
- return false;
- }
- if (data > node.data) {
- return find(node.right, data);
- } else if (data < node.data) {
- return find(node.left, data);
- } else {
- return true;
- }
- }
- public void targetSumPair(Node root, Node node, int tar) {
- if (node == null) {
- return;
- }
- targetSumPair(root, node.left, tar);
- int comp = tar - node.data;
- if (comp > node.data) {
- if (find(root, comp)) {
- t=true;
- System.out.println(node.data + " " + comp);
- }
- }
- targetSumPair(root, node.right, tar);
- }
- public void targetSum(Node root, int tar)
- {
- targetSumPair(root, root, tar);
- if(t==false)
- System.out.println(-1);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement