HackerRankSolutions/LowestCommonAncestor.java at master · Pradyuman7/HackerRankSolutions · GitHub

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.*;
import java.io.*;

class Node {
    Node left;
    Node right;
    int data;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {

	/*
    class Node
    	int data;
    	Node left;
    	Node right;
	*/
	public static Node lca(Node root, int v1, int v2) {
        Node temp = root;

        while (true) {
            if (temp.data > v1 && temp.data > v2) {
            temp = temp.left;
            }
            else if (temp.data < v1 && temp.data < v2) {
            temp = temp.right;
            }
            else {
            return temp;
            }
        }

    }

    public static Node parent(Node currentRoot, Node p) {
        if (currentRoot == null)
            return null;

        else{

            if(currentRoot.left == p || currentRoot.right == p)
                return currentRoot;

            else {

                if (currentRoot.data < p.data)
                    return parent(currentRoot.right, p);

                else
                    return parent(currentRoot.left, p);

            }
        }
    }

    public static Node inOrderSearch(Node node, int v1){

        if(node.left != null)
            return inOrderSearch(node.left,v1);

        if(node.data == v1)
            return node;

        if(node.right != null)
            return inOrderSearch(node.right,v1);

        return node;
    }

	public static Node insert(Node root, int data) {