Ein markierter Binärbaum B ist ein natürlicher binärer Suchbaum (kurz: binärer Suchbaum), wenn die Suchbaum-Eigenschaft gilt, d.h. wenn für jeden Knoten K in B gilt:

• Alle Schlüssel im linken Unterbaum von K sind echt kleiner als der Schlüssel von K .
• Alle Schlüssel im rechten Unterbaum von K sind echt größer als der Schlüssel von K .

• „Natürlich“ bezieht sich auf das Entstehen der Bäume in Abhängigkeit von der Reihenfolge der Einfüge-Operationen (Abgrenzung zu balancierten Bäumen).
• In einem binären Suchbaum gibt es zu einem Schlüssel maximal einen Knoten mit entsprechender Markierung.