Wireless Mesh Networks (WMNs) are important networking infrastructure for providing cost-efficient broadband wireless connectivity. Mesh router node placement is important to achieve network connectivity and coverage in such networks. In this paper, we compare the performance of Genetic Algorithm (GA) and Hill Climbing (HC) for mesh router node placement in WMNs. We consider Exponential and Weibull distributions of mesh clients and grid size 16x16, 32x32 and 64x64. As evaluation metric we used size of giant component. Simulation results show that GA performs better than HC.