Как найти узел двоичного дерева поиска без использования рекурсивного метода

Question

Если у меня есть метод, который принимает только значение в качестве аргумента (не узел) с именем public Node finder (E val), как я могу найти соответствующий узел независимо от высоты и ширины дерева. Если бы метод использовал Node в качестве аргумента, было бы простым решением использовать рекурсию. Но, к сожалению, мне не разрешено изменять подпись метода. Как я могу сделать это умным способом, а не тупым способом, который я пытаюсь ниже, который просто закончится тонной встроенных if функций

public class BinarySearchTree<E extends Comparable<E>> {
    class Node {
        E value;
        Node leftChild = null;
        Node rightChild = null;
        Node(E value) {
            this.value = value;
        }
    }

    public Node finder(E val) {
        
        if (val == null) return null;
        if (root == null) return null;
        
        boolean flag = false;  
        Node temp = root;
        
        //find if Root Node matches value
        if(temp.value.compareTo(val) == 0) {
            flag = true;
            return temp;
        } 
        //if value is less than root check the left branch
        else if (temp.value.compareTo(val) > 0) {
            
            if(temp.leftChild.value.compareTo(val) == 0) {
                flag = true;
                return temp.leftChild;
            } 
            //more if statements here
        } 
        //if value is more than root check the right branch 
        else {
            if(temp.rightChild.value.compareTo(val) == 0) {
                flag = true;
                return temp.rightChild;
            }
            
            //more if statements here
        }
        
        return null;
    }
}

Answer 1

Деревья двоичного поиска обладают этим интересным свойством:

• Левое поддерево узла содержит только узлы со значениями, меньшими, чем значение узла.
• Правое поддерево узла содержит только узлы со значением, превышающим ключ узла.

Предполагая, что ваш класс BinarySearchTree содержит ссылку на root, вы можете перемещаться по двоичному дереву итеративно , пока вы не выполните достичь значения или достичь листового узла, что означает, что ваше значение не существует в вашем двоичном дереве поиска. Временная сложность этой операции поиска составляет O (log (n)).

Вот какой-то псевдокод

Find-Node(val):

    node = root
    while node != null:
      if val == node.val then return root
      if val < node.val then node = node.left
      if val > node.val then node = node.right

    return null