Lowest Common Ancestor of the deepest leaves of a Binary Tree

  

#include <bits/stdc++.h>

using namespace std;

  

struct Node {

    struct Node* left;

    struct Node* right;

    int data;

};

  

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->data = key;

    temp->left = temp->right = NULL;

    return temp;

}

  

int finddepth(Node* root)

{

    

    if (!root)

        return 0;

  

    

    int left = finddepth(root->left);

  

    

    int right = finddepth(root->right);

  

    

    return 1 + max(left, right);

}

  

Node* dfs(Node* root, int curr,

          int depth)

{

    

    if (!root)

        return NULL;

  

    

    if (curr == depth)

        return root;

  

    

    Node* left = dfs(root->left,

                     curr + 1, depth);

  

    

    Node* right = dfs(root->right,

                      curr + 1, depth);

  

    

    if (left != NULL && right != NULL)

        return root;

  

    

    

    return left ? left : right;

}

  

Node* lcaOfDeepestLeaves(Node* root)

{

    

    if (!root)

        return NULL;

  

    

    

    int depth = finddepth(root) - 1;

  

    

    

    return dfs(root, 0, depth);

}

  

int main()

{

    

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5);

    root->right->left = newNode(6);

    root->right->right = newNode(7);

    root->right->left->left = newNode(8);

    root->right->left->right = newNode(9);

  

    cout << lcaOfDeepestLeaves(root)->data;

  

    return 0;

}

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets