Lowest Common Ancestor of Deepest Leaves

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

• The node of a binary tree is a leaf if and only if it has no children
• The depth of the root of the tree is 0. if the depth of a node is d, the depth of each of its children is d + 1.
• The lowest common ancestor of a set S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.

Example 1:

Input: root = {3,5,1,6,2,0,8,null,null,7,4}
Output: [2,7,4]

Approach

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LowestCommonAncestorDeepestLeaves {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        TreeNode lcaDeep = lcaDeepestLeaves(root);

        printTree(lcaDeep);
    }

    // function to find the lca of the
    // given nodes
    static TreeNode LCA(TreeNode root, int val1, int val2) {

        // base case if tree is empty
        if (root == null)
            return null;

        // root val is same as of any given value
        // then lca is the root node
        if (root.val == val1 || root.val == val2)
            return root;

        // call for left lca
        TreeNode leftLCA = LCA(root.left, val1, val2);

        // call for right lca
        TreeNode rightLCA = LCA(root.right, val1, val2);

        // if left and right lca are not null then
        // the lca will we the root node
        if (leftLCA != null && rightLCA != null)
            return root;

        // if left lca null then return right
        if (leftLCA == null)
            return rightLCA;

        // else return left
        return leftLCA;

    }

    // function to find the lca of deepest
    // leaf nodes
    static TreeNode lcaDeepestLeaves(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null)
            return null;
        q.add(root);
        while (!q.isEmpty()) {
            int len = q.size();
            List<Integer> v = new ArrayList<Integer>();
            while (len > 0) {
                len--;
                TreeNode temp = q.poll();
                v.add(temp.val);
                if (temp.left != null)
                    q.add(temp.left);
                if (temp.right != null)
                    q.add(temp.right);
            }
            res.add(v);
        }
        List<Integer> v = res.get(res.size() - 1);
        if (v.size() == 1) {
            TreeNode ans = LCA(root, v.get(0), v.get(0));
            return ans;
        }
        int x = v.get(0);
        TreeNode ans = null;
        for (int i = 1; i < v.size(); i++) {

            int y = v.get(i);
            ans = LCA(root, x, y);

            if (ans != null)
                x = ans.val;
        }
        return ans;
    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            root = q.poll();
            if (root == null)
                vec.add("null");
            else
                vec.add(String.valueOf(root.val));
            if (root != null) {
                q.add(root.left);
                q.add(root.right);
            }
        }
        int j = vec.size() - 1;
        while (j > 0 && vec.get(j) == "null")
            j--;
        for (int i = 0; i < j; i++)
            System.out.print(vec.get(i) + ",");
        System.out.print(vec.get(j));
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
}; 

//function to find the lca of the
//given nodes
TreeNode *LCA(TreeNode *root,int val1,int val2)
{

     //base case if tree is empty
     if(root==NULL)
         return NULL;

     //root data is same as of any given value
     //then lca is the root node
     if(root->data==val1||root->data==val2)
         return root;

     //call for left lca
     TreeNode *leftLCA=LCA(root->left,val1,val2);

     //call for right lca
      TreeNode *rightLCA=LCA(root->right,val1,val2);


    //if left and right lca are not null then
    //the lca will we the root node
     if(leftLCA!=NULL&&rightLCA!=NULL)
              return root;

    //if left lca null then return right  
    if(leftLCA==NULL)
              return rightLCA;

     //else return left
     return leftLCA;
        
}

//function to find the lca of deepest 
//leaf nodes
TreeNode* lcaDeepestLeaves(TreeNode* root) 
{
        queue<TreeNode*> q;
        vector<vector<int>> res;
        if(root==NULL)
              return NULL;
        q.push(root);
        while(!q.empty())
        {
            int len=q.size();
            vector<int> v;
            while(len--)
            {
                TreeNode *temp=q.front();
                q.pop();
                v.push_back(temp->data);
                if(temp->left)
                      q.push(temp->left);
                if(temp->right)
                       q.push(temp->right);
            }
            res.push_back(v);
        }
        vector<int> v=res[res.size()-1];
        if(v.size()==1)
        {
            TreeNode *ans=LCA(root,v[0],v[0]);
            return ans;
        }
         int x=v[0];
        int flag=0;
        TreeNode *ans=NULL;
        for(int i=1;i<v.size();i++) 
        {
          
            int y=v[i];
            ans=LCA(root,x,y);
            
            if(ans!=NULL)
             x=ans->data;
        } 
        return ans;   
}

//function to print the tree
void printTree(TreeNode *root)
{
    queue<TreeNode*>q;
    q.push(root);
    vector<string> vec;
    while(!q.empty())
     {
         root=q.front();
         q.pop();
         if(root==NULL)
            vec.push_back("null");
         else
            vec.push_back(to_string(root->data));
        if(root!=NULL)
          {
              q.push(root->left);
              q.push(root->right);
          }
     }
     int j=vec.size()-1;
     while(j>0&&vec[j]=="null")
        j--;
      vec.resize(j);
      for(int i=0;i<j;i++)
        cout<<vec[i]<<",";
      cout<<vec[j];
}
int main()
{
    TreeNode *root=new TreeNode(3);
    root->left=new TreeNode(5);
    root->right=new TreeNode(1);
    root->left->left=new TreeNode(6);
    root->left->right=new TreeNode(2);
    root->right->left=new TreeNode(0);
    root->right->right=new TreeNode(8);
    root->left->right->left=new TreeNode(7);
    root->left->right->right=new TreeNode(4);

    TreeNode *lcaDeep=lcaDeepestLeaves(root);

    printTree(lcaDeep);
    return  0;

}