Поиск размера BST в Java

Question

Я пытаюсь найти размер BST с помощью этого фрагмента кода.

public static void main(String[] args) { 

     BST bst = new BST(); 
     int [] arr = {12, 15,7,3,81, 9}; 
     for (int i = 0; i <arr.length; i++) { 
      bst.add(arr[i]); 
     } 

     System.out.print(size(bst.root)); 

    } 
    public static int size(Node node){ 
     if (node != null) { 
      return size(node.left) +1 + size(node.right) + 1; 
     }else 
      return 0; 
    } 

Ответ, который я получаю, это 12, что является первым элементом. Что я делаю неправильно?

Answer 1

Причина, по которой вы получаете 12, состоит в том, что ваш код дважды возвращает количество элементов в дереве (из которых 6). Тот факт, что 12 также является первым элементом, является чисто совпадением.

return заявление следует читать:

return 1 + size(node.left) + size(node.right); 

т.е. этот узел плюс размер левого поддерева плюс размер правого поддерева.

Второй +1 у вас есть ошибочный.

Answer 2

Вы используете двойной счет. Здесь нужен только один +1.