Advertisement
Guest User

Untitled

a guest
Nov 19th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.15 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.nio.charset.StandardCharsets;
  5. import java.util.stream.IntStream;
  6.  
  7. public class Main{
  8. public static void main(String args[]) throws IOException {
  9. InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
  10. BufferedReader in = new BufferedReader(reader);
  11. String line;
  12. String input = "";
  13. while ((line = in.readLine()) != null) {
  14. input = line;
  15. }
  16. String[] parts = input.split(" ");
  17. int node1 = Integer.parseInt(parts[0]);
  18. int node2 = Integer.parseInt(parts[1]);
  19.  
  20. int[] node_vals = new int[]{30,8,52,3,20,10,29};
  21. if(IntStream.of(node_vals).noneMatch(x -> x == node1)){
  22. System.out.print("Value "+ node1 + " does not exist in a tree");
  23. }
  24. if(IntStream.of(node_vals).noneMatch(x -> x == node2)){
  25. System.out.print("Value "+ node2 + " does not exist in a tree");
  26. }
  27.  
  28. BinaryTree tree = new BinaryTree();
  29. tree.root = new Node(30);
  30. tree.root.left = new Node(8);
  31. tree.root.right = new Node(52);
  32. tree.root.left.left = new Node(3);
  33. tree.root.left.right = new Node(20);
  34. tree.root.left.right.left = new Node(10);
  35. tree.root.left.right.right = new Node(29);
  36.  
  37. Node t = tree.lca(tree.root, node1, node2);
  38. System.out.println(t.data);
  39. }
  40. }
  41.  
  42. class Node {
  43. int data;
  44. Node left, right;
  45.  
  46. Node(int item) {
  47. data = item;
  48. left = right = null;
  49. }
  50. }
  51.  
  52. class BinaryTree {
  53. Node root;
  54.  
  55. Node lca(Node node, int n1, int n2) {
  56. if (node == null)
  57. return null;
  58.  
  59. // If both n1 and n2 are smaller than root, then LCA lies in left
  60. if (node.data > n1 && node.data > n2)
  61. return lca(node.left, n1, n2);
  62.  
  63. // If both n1 and n2 are greater than root, then LCA lies in right
  64. if (node.data < n1 && node.data < n2)
  65. return lca(node.right, n1, n2);
  66.  
  67. return node;
  68. }
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement