BinaryTree/distance_between_two_nodes_of_binary_tree.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
108
109
110
111
112
113
114
#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 findLCA1(node* root, node* &lca, node* x, node* y,int & distance )
{

    if (root == NULL)
        return 0;

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

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

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

    if (left && right){
        lca = root;

    }

    if (left || right) distance++;

    return left || right;
}

int findLevel(struct node * root ,struct node * node,int level){
    if (root == NULL) return INT_MIN;
    if (root == node) return level;
    int left = findLevel(root->left,node,level+1);
    if(left !=  INT_MIN) return left;
    return findLevel(root->right,node,level+1);

}

// Function to find lowest common ancestor of nodes x and y
int findDistance(node* root, node* x, node* y)
{
    int distance = 0;
    struct node *lca = NULL;

    if (isNodePresent(root, y) && isNodePresent(root, x))
        findLCA1(root, lca, x, y,distance);

    return findLevel(lca, x, 0) + findLevel(lca, y, 0);
}


// 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);

    printf("%d is ditance between %d and %d",findDistance(root,root->right->left->left, root->left->right),root->right->left->left->key,root->left->right->key);

    return 0;
}