- Data Structures, DFS, LCA, Recursion, Searching, Tree, tree-traversal

Lowest Common Ancestor of the deepest leaves of a Binary Tree

  #include 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 data;      return 0;}