CodingInterview/cloudera2.cpp at master · ssripadham/CodingInterview · 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
77
78
79
80
81
82
83
84
85

/**
 * Given an unsorted tree of unique elements, find the common
 * ancestor of two nodes. For example, given this tree:
 *
 *              5
 *             / \
 *            6   3
 *           / \
 *          9   1
 *               \
 *                8
 *
 * commonAncestor(9,1) == 6
 * commonAncestor(1,3) == 5
 * commonAncestor(6,1) == 5
 * commonAncestor(9,8) == 6
 */

class Tree {
    struct Node {
        // should be unique in the tree
        int value;

        // child nodes
        Node* left;
        Node* right;
    };

    Node* mRoot;

    Node* findUtil(Node* root, Node* a){

        if (root == NULL || a == NULL) {
            return NULL;
        }

        if (root->data == a->data) {
            return root;
        }

        if findUtil(root->left, a) return root->left;
        if findUtil(root->right, a) return root->right;

        return NULL;
    }


    struct Node* commonAncestorUtil(struct Node* a, struct Node* b, struct Node* root, struct node* parent) {

        if (root == NULL) return NULL;

        if (a = NULL || b == NULL) return root;

        if ((root->right = a  && root->left = b) || (root->left = a && root->right = b) {
            return root;
        }


        bool aIsLeft = findUtil(root->left,a) != NULL;
        bool aIsRight = findUtil(root->right,a) != NULL;

        bool bIsLeft = findUtil(root->left, b) != NULL;
        bool bIsRight = findUtil(root->right,b) != NULL;


        if (aIsLeft && bIsRight || aIsRight && bIsLeft) {
            return root;
       }

       if (aIsLeft && bIsLeft) return commonAncestor(a, b, root->left, root);

       if (aIsRight && bIsRight) return commonAncestor(a,b, root->right, root);

       return NULL;

    }


}