Question: Let T be an n-node tree rooted at some node r. We want to place as few guards as possible on nodes of T, such that every edge of T is guarded: an edge between a parent node v and its child w is guarded if one places a guard on at least one of these two nodes v, w. Give an O(n) time algorithm for finding an optimal solution to the problem.
My approach was to do post order traversal from the root and place a guard on a node that is part of an unguarded edge except if that node is a leaf...but this algorithm wouldn't work if all the nodes were arranged in a linear chain because my algorithm would place guards on every node except for the ends of the chain.
I've looked online and checked out the DP solutions, which make sense to me but I was wondering if there's a greedy algorithm to find a vertex cover for a tree