**PROBLEM LINK:** Is it Sorted or Not, That is the Question

**AUTHOR:** panik

**DIFFICULTY:** Easy-Medium

**PREREQUISITES:** Graph Theory, DFS

Solution: In This Problem, we can see that the maximum no. of connected

components that we can get if we had the opportunity to delete any kind of node (not

just the leaf node) we could have obtained the answer to be total no. of leaf nodes in

the graph ( We can prove that there always exist a way to get this many connected

components).

Now Since we can delete only the leaf node, so each operation

would result in one less connected component than the max we could have

obtained(count of leaf nodes), because after every operation 1 leaf node is

destroyed. So we choose only those leaf nodes whose destruction is

mandatory and their destruction results in the creation of at least 1 additional

connected component.

Now how to find the count of leaf nodes to be destroyed?

For this we need to observe that, there are 2 types of leaf nodes, 1) Such leaf nodes

whose parent has only leaf nodes as children and 2) whose parents have mixed

children(leaf node and non-leaf nodes).

For this Question, you also need to understand that such nodes that have only 1 child

can be compressed. eg. Tree of 7 nodes connections made like:

1 2

2 3

1 4

4 5

1 6

6 7

can be replaced with a tree of 4 nodes with connections like:

1 2

1 3

1 4

which is basically replacing linear chain of nodes with a single node,

and the answer to the above problem still remains the same i.e 2(we can delete any

leaf node and 2 components will remain).

So now letâ€™s assume that whatever tree we get through input, we compress it using

the following property. Now coming back to the original question, we find the count of

all such nodes that have only leaf nodes as its children and subtract this count from

the max answer possible(total no. of leaf nodes). This method is correct because all

such nodes which have only leaf nodes as children have to have any one of its leaf

node destroyed to free the other leaf nodes.

Now we can avoid the compression of the tree by smartly implementing DFS only

once and finding all such nodes. So complexity is O(N).

**Expected solution**: here