Obhod binarnih (pod)dreves

Pozdravljeni, rad bi napisal neko funkcijo, ki pri (ne nujno) urejenem binarnem drevesu oz. poddrevesu preveri neko lastnost.
Binarna drevesa imam sestavljena, tako da vsebujejo (int)vredost, ter kazalca na levega in desnega otroka.
Primer je npr. boolean funckija, ki bi preverila, če v (pod)drevesu obstaja kakšna negativna vrednost, ki nima obeh otrok?

Problema sem se lotil rekurzivno, ampak mi nikakor ne deluje. Bi lahko kdo vsaj približno opisal postopek?

		public boolean lahkoDodamo(BNode node){
			if(node == null ) return true;
			else if(node != null){
				if(node.value < 0){
					if(node.left == null || node.right == null){
						return true;
					}
				}
				lahkoDodamo(node.left);
				lahkoDodamo(node.right);
				
			}
			
			return false;
		}

Vem, da je težava da pride na zadnji return false preden preveri vse možnosti, ampak ne vem kako naj naredim drugače.
Java zahteva return stavek, ker je funkcija tipa boolean. Kako se lotiti takega problema?

Pa malo polepšaj/preuredi if stavke, ker tole je precej neberljivo.