Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.nio.charset.StandardCharsets;
- import java.util.stream.IntStream;
- public class Main{
- public static void main(String args[]) throws IOException {
- InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
- BufferedReader in = new BufferedReader(reader);
- String line;
- String input = "";
- while ((line = in.readLine()) != null) {
- input = line;
- }
- String[] parts = input.split(" ");
- int node1 = Integer.parseInt(parts[0]);
- int node2 = Integer.parseInt(parts[1]);
- int[] node_vals = new int[]{30,8,52,3,20,10,29};
- if(IntStream.of(node_vals).noneMatch(x -> x == node1)){
- System.out.print("Value "+ node1 + " does not exist in a tree");
- }
- if(IntStream.of(node_vals).noneMatch(x -> x == node2)){
- System.out.print("Value "+ node2 + " does not exist in a tree");
- }
- BinaryTree tree = new BinaryTree();
- tree.root = new Node(30);
- tree.root.left = new Node(8);
- tree.root.right = new Node(52);
- tree.root.left.left = new Node(3);
- tree.root.left.right = new Node(20);
- tree.root.left.right.left = new Node(10);
- tree.root.left.right.right = new Node(29);
- Node t = tree.lca(tree.root, node1, node2);
- System.out.println(t.data);
- }
- }
- class Node {
- int data;
- Node left, right;
- Node(int item) {
- data = item;
- left = right = null;
- }
- }
- class BinaryTree {
- Node root;
- Node lca(Node node, int n1, int n2) {
- if (node == null)
- return null;
- // If both n1 and n2 are smaller than root, then LCA lies in left
- if (node.data > n1 && node.data > n2)
- return lca(node.left, n1, n2);
- // If both n1 and n2 are greater than root, then LCA lies in right
- if (node.data < n1 && node.data < n2)
- return lca(node.right, n1, n2);
- return node;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement