javaでclass Nodeをつくりました。
図３の関数addNodeもついています。

class Node {
    int key;
    Node left;
    Node right;
    
    Node addNode(int k,Node p){
      if(p.key == 0) {
          p.key = k;
      } else if(k != p.key){
          if(k < p.key){
              p.left = addNode(k,new Node());
          } else {
              p.right = addNode(k,new Node());
          }
      }
      return p;
    }
}
図１にならって下記のテストクラスを実行すると、
class AP27akiTest {
    public static void main(String[] args){
        Node n = new Node();
        n = n.addNode(15,n);
        n = n.addNode(8,n);
        n = n.addNode(25,n);
        System.out.println(n.key);
        System.out.println(n.left.key);
        System.out.println(n.right.key);
    }
}
出力は、
１５
８
２５
と表示されました。
次に２と２０も追加して実行すると、
class AP27akiTest {
    public static void main(String[] args){
        Node n = new Node();
        n = n.addNode(15,n);
        n = n.addNode(8,n);
        n = n.addNode(25,n);
        n = n.addNode(2,n);
        n = n.addNode(20,n);
        System.out.println(n.key);
        System.out.println(n.left.key);
        System.out.println(n.right.key);
        System.out.println(n.left.left.key);
        System.out.println(n.right.left.key);
    }
}
出力は、
１５
２
２０
とNullPointerExceptionが表示されました。
８と２５の次にNodeが生成されずに上書きされています。
なぜでしょう？

ご提示されてるコードには探索部分が無いので、ただの２分木ですね。