Binary Search Tree : Lowest Common Ancestor

  • + 0 comments

    solution in C++

    #include <bits/stdc++.h>
    
    using namespace std;
    
    class Node {
        public:
            int data;
            Node *left;
            Node *right;
            Node(int d) {
                data = d;
                left = NULL;
                right = NULL;
            }
    };
    
    class Solution {
        public:
      		Node* insert(Node* root, int data) {
                if(root == NULL) {
                    return new Node(data);
                } else {
                    Node* cur;
                    if(data <= root->data) {
                        cur = insert(root->left, data);
                        root->left = cur;
                    } else {
                        cur = insert(root->right, data);
                        root->right = cur;
                   }
    
                   return root;
               }
            }
    
    /*The tree node has data, left child and right child 
    class Node {
        int data;
        Node* left;
        Node* right;
    };
    
    */
        vector<int> pathNode(Node *root, int x) {
            vector<int> res;
            if (!root) {
                return res;
            }
            while (root -> data != x) {
                if (root -> data == x) {
                    res.push_back(x);
                    return res;
                }
                else if (root -> data > x) {
                    res.push_back(root -> data);
                    root = root -> left;
                }
                else {
                    res.push_back(root -> data);
                    root = root -> right;
                }
            }
            res.push_back(x);
            return res;
        }
        Node *lca(Node *root, int v1,int v2) {
    		// Write your code here.
            Node * node = root;
            if (v1 > root -> data && v2 < root -> data) {
                return root;
            }
            if (v1 < root -> data && v2 > root -> data) {
                return root;
            }
            vector<int> s1 = pathNode(root, v1);
            vector<int> s2 = pathNode(root, v2);
            int temp = 0;
            int count = 0;
            for (int i = s1.size() - 1; i >= 0 ; i--) {
                if (count != 0) {
                    break;
                }
                for (int j = s2.size() - 1; j >= 0; j--) {
                    if (s1[i] == s2[j]) {
                        temp = s1[i];
                        count++;
                        break;
                    }
                }
            }
            // cout << temp << endl;
            while (node -> data != temp) {
            if (node -> data == temp) {
                return node;
            }   
            else if (node -> data > temp) {
                node = node -> left;
            }
            else {
                node = node -> right;
            }
            }
            return node;
        }
    
    }; //End of Solution
    
    int main() {
      
        Solution myTree;
        Node* root = NULL;
        
        int t;
        int data;
    
        std::cin >> t;
    
        while(t-- > 0) {
            std::cin >> data;
            root = myTree.insert(root, data);
        }
      	
      	int v1, v2;
      	std::cin >> v1 >> v2;
      
        Node *ans = myTree.lca(root, v1, v2);
        
      	std::cout << ans->data;
    
        return 0;
    }