LCA - Amazon Live Coding

LCA-Amazon.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <utility>      // std::pair, std::make_pair
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <sstream>
#include <chrono>
#include <ctime>

using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node* parent;
    
    Node(int x): val(x), left(NULL), right(NULL), parent(NULL) {}
};

// A function creates a new binary tree node with given value and parent node
Node * newNode(int value, Node *parent){
    
    Node *node = new Node(value);
    node->val = value;
    node->parent = parent;
    node->left = node->right = NULL;
    
    return node;
}

int getHeight(Node *n) {
    int cunt = 0;
    while (n != NULL) {
        cunt ++;
        n = n->parent;
    }
    
    return cunt;
}


int LCADistanceWithParent(Node *p, Node *q){
    int hp = getHeight(p);
    int hq = getHeight(q);
    
    // we assume hp at depth >= hq
    if (hq > hp) {
        swap(p, q);
        swap(hp, hq);
    }
    
    int diff = hp - hq;
    int result = diff;

    while(diff--) {
        p = p->parent;
    }
    
    // both now are at the same level
    // if no LCA, both will be NULL, and so terminate
    while (p != q) {
        p = p->parent;
        q = q->parent;
        result+=2;
    }
    
    if (p == NULL) {
        return -1;
    }
    
    return result;
}

bool findNode(Node *current, int goal, vector<Node*> &path) {
    
    if(current == NULL) {return false;}

    path.push_back(current);
    
    if (current->val == goal) {
        return true;
    }
    
    if (findNode(current->left, goal, path) ||
        findNode(current->right, goal, path)) {
        return true;
    }
    
    path.pop_back();
    return false;
}

int LCADistance(Node* root, Node* p, Node* q) {
    vector<Node*> path_p;
    vector<Node*> path_q;
    
    if (!findNode(root, p->val, path_p) ||
        !findNode(root, q->val, path_q)) {
        return  -1;
    }
    
    
    int i = 0;
    for(; i < path_p.size() && i < path_q.size(); i++) {
        if (path_p[i]->val != path_q[i]->val) {
            break;
        }
    }
    
    int result = 0;
    result += (path_p.size() - i);
    result += (path_q.size() - i);

    
    return result;
}


int main() {
    
    // Create the Binary Tree as shown below
    /*
             _______1______
            /              \
            ___2__        ___3__
           /      \      /      \
          4       5     6       7
         /
        8
     
    */
    
    Node * root = newNode(1, NULL);
    root->left    = newNode(2, root);
    root->right = newNode(3, root);
    
    root->left->left            = newNode(4, root->left);
    Node *q = root->left->right = newNode(5, root->left);
    root->right->left            = newNode(6, root->right);
    root->right->right            = newNode(7, root->right);
    
    Node *p = root->left->left->left = newNode(8, root->left->left);
    
    
    // Q: What if they are on the same path such as 4 & 8?
    cout<<LCADistanceWithParent(p, q)<<endl;
    cout<<LCADistance(root, p, q)<<endl;

    return 0;
}