Leetcode — 865. Smallest Subtree with all the Deepest Nodes

The link to the problem: https://leetcode.com/problems/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:

Photo credit to Leecode

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

Thoughts:

The problem asks us to return the deepest node of the tree. If there’s more than one deepest node of the whole tree, then we should return the smallest subtree that contains all these deepest nodes. (You can also say that we should return their lowest ancestor nodes.)

My idea of solving this problem is to traverse all the nodes level by level. We can actually narrow down the possible nodes of our answer by using their height, or let’s say “the distance from the node to its child leaf node”.

👷Difference between a HEIGHT and a DEPTH: 
1. The depth of a node is the number of edges from the node to the root. Hence, the deepest node of the tree will have the highest depth and the depth of the root is 0.
2. The height is kind of the opposite. It means the number of edges from the node to its deepest leaf child node. Hence, a leaf node will have a height of 0.
▶️▶️ When we usually say the nodes are in the same level, that means these nodes have the same depths. However, it is possible that they might have different heights.

Let’s use several examples to see what I meant.

If I have three trees shown below:

Example Trees

In the above graph, the orange nodes are the root of our answer subtree. I labeled the heights of the nodes so that it will be easier for us to find any interesting perspective. We can tell that the more the height of the node is, the further the node is to reach its leaf node. i.e., When we have a node whose height is larger than its sibling or cousin nodes, this node will lead us to the path of finding the deepest node of the tree. That is to say, we can narrow down the range of the answer nodes since we will just abandon the other nodes.

Code Logic:

Now, let’s convert the above idea into the code logic.

Since we are going to traverse the tree level by level, we are going to put the nodes into the queue. However, we are not going to put all the nodes into the queue, we will only select one node that has a higher height than other nodes in the same level.

You might be wondering, isn’t it possible that there are more than one nodes that have a higher height than other nodes on the same level? You need to know, we do not really compare ALL the nodes on a certain level of the given tree. Since we traverse the tree from the top, we will always choose one node at a time. Hence, that’s why our queue will always contain one node. No need to worry that we don’t know which node to choose if more than one node meets the condition since there are only at most 2 nodes (i.e., the current node’s left node and right node) that we are going to pick for the next level.

What we are going to do in each iteration is to get two heights of the current node’s left node and right node. We will then compare these two heights:

1. If the heights of two child nodes are the same: the current node is our answer node since both of the child nodes “have access” to the deepest nodes of the tree.
2. Either one of the nodes has a deeper height: the node might be the deepest node or the parent of the deepest node(s). We are not sure yet, so we will just place the node into the queue and observe it in the next iteration. Also, we will abandon the unchosen node by not placing it in the queue.

Below is the 0ms code that beats 100% —

public TreeNode subtreeWithAllDeepest(TreeNode root) {
        if(root.left==null && root.right==null)
            return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty())
        {
            TreeNode node = queue.poll();
            int leftH = height(node.left, 0);
            int rightH = height(node.right, 0);
            if(leftH == rightH)
                return node;
            if(leftH > rightH) //abandon the right node
                queue.offer(node.left);
            else 
                queue.offer(node.right);
        }
        return null;
    }
    //distance from node to leaf node
    public int height(TreeNode node, int count){
        if(node==null)
            return count-1;
        int leftH = height(node.left, count+1);
        int rightH = height(node.right, count+1);
        return Math.max(leftH, rightH);
    }

Or we can use a TreeNode instead of using a queue since we actually always store one node in the queue at a time:

public TreeNode subtreeWithAllDeepest(TreeNode root) {
        TreeNode node = root;
        while(node!=null)
        {
            int leftH = height(node.left, 0);
            int rightH = height(node.right, 0);
            if(leftH == rightH)
                return node;
            if(leftH > rightH)
                node = node.left;
            else 
                node = node.right;
        }
        return null;
    }
    public int height(TreeNode node, int count){
        if(node==null)
            return count-1;
        int leftH = height(node.left, count+1);
        int rightH = height(node.right, count+1);
        return Math.max(leftH, rightH);
    }