BinaryTree/lowest_common_ancestor_.cpp at master · arpansahu/BinaryTree · 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <stdio.h>
#include <malloc.h>
#include <limits.h>

/* nodes for queue and tree node*/
struct node {
    int key;
    struct node * left;
    struct node * right;
};

/* function for creating new node of tree*/
struct node *newNode(int data)
{
    struct node *node = (struct node *)malloc(sizeof(struct node));
    node->key = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}


// Function to find aall the paths from the root
int isNodePresent(node* root, node* node)
{

    if (root == NULL)
        return 0;

    if (root == node)
        return true;

    return isNodePresent(root->left, node) ||
           isNodePresent(root->right, node);
}


int findLCA(node* root, node* &lca, node* x, node* y)
{

    if (root == NULL)
        return 0;

    if (root == x || root == y)
    {
        lca = root;
        return 1;
    }

    bool left = findLCA(root->left, lca, x, y);

    bool right = findLCA(root->right, lca, x, y);

    if (left && right)
        lca = root;

    return left || right;
}

// Function to find lowest common ancestor of nodes x and y
void findLCA(node* root, node* x, node* y)
{

    node *lca = NULL;

    if (isNodePresent(root, y) && isNodePresent(root, x))
        findLCA(root, lca, x, y);

    if (lca != NULL)
        printf("LCA is %d \n",lca->key);
    else
        printf("LCA do not exist\n");
}

// main function
int main()
{
    struct node*     root = newNode(1);
    /* Construct below tree
          1
        /   \
       /     \
      2       3
       \     / \
        4   5   6
           / \
          7   8
    */


    root->left = newNode(2);
    root->right = newNode(3);
    root->left->right = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->left = newNode(7);
    root->right->right->right = newNode(8);

    findDistance(root, root->right->left->left, root->right->right);
    findDistance(root, root->right->left->left, newNode(10));
    findDistance(root, root->right->left->left, root->right->left->left);
    findDistance(root, root->right->left->left, root->right->left);
    findDistance(root, root->left, root->right->left);

    return 0;
}