Smallest Subtree with all the Deepest Nodes

Given the root of a binary tree, the depth of each node is the shortest distance to the root.
Return the smallest subtree such that it contains all the deepest nodes in the original tree.
A node is called the deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

Example 1:

Input: root = {0,1,3,null,2}
Output: [2]

Approach

Java

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

public class SmallestSubtreeDeepestNodes {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(2);

        TreeNode sub = subtreeWithAllDeepest(root);
        printTree(sub);
    }

    static TreeNode LCA(TreeNode root, int val1, int val2) {
        if (root == null)
            return null;
        if (root.val == val1 || root.val == val2)
            return root;
        TreeNode leftLCA = LCA(root.left, val1, val2);
        TreeNode rightLCA = LCA(root.right, val1, val2);
        if (leftLCA != null && rightLCA != null)
            return root;
        if (leftLCA == null)
            return rightLCA;
        return leftLCA;

    }

    static TreeNode subtreeWithAllDeepest(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;
    }
};
TreeNode *LCA(TreeNode *root,int val1,int val2)
{
        if(root==NULL)
              return NULL;
        if(root->data==val1||root->data==val2)
               return root;
        TreeNode *leftLCA=LCA(root->left,val1,val2);
        TreeNode *rightLCA=LCA(root->right,val1,val2);
        if(leftLCA!=NULL&&rightLCA!=NULL)
              return root;
        if(leftLCA==NULL)
              return rightLCA;
        return leftLCA;
        
}
TreeNode* subtreeWithAllDeepest(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;
}
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(0);
    root->left=new TreeNode(1);
    root->right=new TreeNode(3);
    root->left->right=new TreeNode(2);
    
    TreeNode *sub=subtreeWithAllDeepest(root);
    printTree(sub);
    return 0;

}