Given a Binary Search Tree and a target number, return
Example 1:
Target = 9
Output: TrueExample 2:
Target = 28
Output: FalseSolution
The problem can be solved with Tree Traversal and maintaining the visited node in HashSet. While traversing a tree we can do lookup in HashSet with valueCode
|
0 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 59 60 61 62 |
import java.util.*; public class TwoSumBST { Set<Integer> set = new HashSet<Integer>(); public static void main(String[] args) { TreeNode node5=new TreeNode(5); TreeNode node3=new TreeNode(3); TreeNode node6=new TreeNode(6); TreeNode node2=new TreeNode(2); TreeNode node4=new TreeNode(4); TreeNode node7=new TreeNode(7); node5.left=node3; node5.right=node6; node3.left=node2; node3.right=node4; node6.right=node7; int k=9; System.out.println(new TwoSumBST().findTarget(node5, k)); } public boolean findTarget(TreeNode root, int k) { if (root == null) return false; //Recursive call to explore left node. if (findTarget(root.left, k)) return true; //Check if K-node.value present in previously visited nodes. if (set.contains(k - root.val)) return true; //Add current node value to Set. set.add(root.val); //Recursive call to explore right node. if (findTarget(root.right, k)) return true; return false; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.
