Smallest Subtree with all the Deepest Nodes

For a binary tree, the depth of each node is the shortest distance to the root. Here a node is deepest if it has the largest depth possible among any node in the entire tree. Clearly, there could be more than one such nodes in a binary tree. A subtree of a node is defined as that node, plus the set of all descendants of that node. We need to find the node with the largest depth such that it contains all the deepest nodes in its subtree.

As shown in the picture above, 7 & 4 are the deepest nodes and 2 is the subtree that contains all the deepest nodes. If you have solved the problem on the Lowest Common Ancestor of two nodes in a binary tree, you might find it very similar to that, except that in this case, the nodes are unknown and there can be any number of them. Let's take a moment to understand the problem

Hopefully, now that we have understood the problem, let's get our hands dirty to find a possible solution. The approach is fairly simple.

We need to do two things

• Find the deepest nodes
• Find their Lowest Common Ancestor

Let's find the deepest nodes first. If we think about it, the deepest nodes could lie

• on the left side of the tree
• on the right side of the tree
• on both on the left side and the right side of the tree

Based on which our Lowest Common Ancestor will be

• the left subtree
• the right subtree
• or the root itself (Think about it..) — We want to cover all the deepest nodes, if they are on both sides, there is only one node that can have all of them- The root

Now each of the subtrees, left or right can be treated as individual trees and we can apply the same approach mentioned above until we find a root that has all the deepest nodes, and that my friend is called the Smallest Subtree with all the Deepest nodes.

But this approach seems very familiar?, yeah you guessed it right, it is famous — Divide & Conquer approach.

For every node, ask the left subtree to get the subtree with the deepest node, ask the right subtree to get the deepest nodes, and compare the depths of the subtree’s returned. Whoever has the maximum depth is the winner. But what if there is a tie?. Well, in that case, clearly the root is the winner.

A typical node in a binary tree would look like this

Since we need to know and define the depths of each node, I choose to create a wrapper around this class to include a field name as depth

If you try to implement the approach we discussed, this is how your solution might look like

I hope you liked the article. If you would want to read more of these, please express the same in the form of claps.