Лучше: дни рождения филиалов на правом и левом берегу.

Правильно, как Вы верно указываете, на берегу. В русском языке есть несколько существительных второго склонения с таким окончанием в предложном падеже со значением места. Ср.: о береге - на берегу, о носе - в носу, о саде - в саду. Падеж один и тот же, окончания (в зависимости от значения падежа) - разные.

Корректен вариант с родительным падежом.

"Дерево" - подлежащее, "береза" - сказуемое.

Да, по мнению некоторых лингвистов (например, Н. М. Шанского), слова берег и беречь этимологически связаны друг с другом. 

Слово берег восходит к индоевропейской основе *bherg'hos и имеет соответствия в других индоевропейских языках: ср. нем. Berg 'гора', норв. berg 'гора; горная цепь', исл. bjarg 'скала, утес', арм. berj 'высота', т. е. первоначальное значение этого индоевропейского корня – 'высота, возвышение', затем – 'гора, гористый берег' и – уже в общеславянском языке – 'берег' вообще (ср. в русских говорах гора – 'возвышенный берег', дорога горой – 'по высокому берегу реки').

Слово беречь восходит к общеслав. *bergti, исходное значение которого – 'прятать, укрывать, защищать'.  Этот глагол тоже имеет соответствия в других индоевропейских языках, ср. нем. bergen 'прятать, закрывать'. Ученые предполагают, что он восходит к той самой индоевропейской основе *bherg'hos. Развитие значения, возможно, шло следующим образом: 'гора' > 'убежище' (гора, углубление в горе служили средством защиты, местом, где можно спрятаться).

См. ответ на вопрос № 279720.

Имя существительное, которому предшествует два или несколько определений, указывающих на разновидности предметов, ставится в форме  единственного числа, если перечисляемые разновидности предметов или явлений внутренне связаны. Таким образом, верно: на правом и левом берегу.