# Codility - Phosphorus - 2014

## Introduction

This is an analysis of Codility - Prosphorus 2014 Challenge.

• This problem is, finding the minimal number of guards to set in a tree which can prevent prisoners escaping to tree leaves.
• Time bound and space bound are both O(N).

## Analysis

• Create a Node structure, holding its parent index, a boolean value presenting it is a prisoner or not. Then a boolean value presenting whether prisoners can escape down to leaves, and another boolean value presenting whether prisoners can escape from the root.
• Depth-First-Search from node 0.
• Adjust the result according to node 0’s state. Done.
• A classic DFS holds time bound and space bound.