Двоичное дерево поиска: Вставка

Question

Я работаю над упражнением Двоичное дерево поиска: Вставка на HackerRank. Вот описание проблемы:

Вам предоставляется указатель на корень двоичного дерева поиска и значение, которое нужно вставить в дерево. Вставьте это значение в соответствующее место в двоичном дереве поиска и верните корень обновленного двоичного дерева. Вам просто нужно выполнить функцию.

Я представил следующее решение и прошел 4 из 6 тестовых случаев и не смог выполнить 2 из 6 тестовых случаев. Проблема заключается в том, что я не могу увидеть два неудачных теста, поэтому я не уверен, почему они не работают. Я попытался создать свои собственные тестовые примеры, и они, похоже, работали правильно. Можете ли вы придумать какие-либо тестовые примеры, на которые мое решение не будет работать? Я надеюсь, кто-то может мне точку в правильном направлении

/* Node is defined as : 
class Node 
int data; 
Node left; 
Node right; 

*/ 

static Node Insert(Node root,int value) 
{ 
    if (root == null){ 
     root = new Node(); 
     root.data = value; 
     return root; 
    } 
    ArrayList<Node> list = new ArrayList<Node>(); 
    list.add(root); 
    getNode(list,value); 
    return root; 
} 

static void getNode(ArrayList<Node> list,int value){ 
    ArrayList<Node> newList = new ArrayList<Node>(); 
    for (int i=0;i<list.size();i++){ 
     newList.add(list.get(i).left); 
     newList.add(list.get(i).right); 
     if(list.get(i).left == null){ 
      list.get(i).left = new Node(); 
      list.get(i).left.data = value; 
      return; 
     } 
     if(list.get(i).right == null){ 
      list.get(i).right = new Node(); 
      list.get(i).right.data = value; 
      return; 
     } 
    } 
    getNode(newList,value); 
} 

Answer 1

статический узел Вставка (корневой узел, INT значение) {

if(root == null) 
    { 
     Node new_node = new Node(); 
     new_node.data=value; 
     root = new_node; 
    } 

if(value < root.data) 
    { 
    if(root.left != null) 
     { 
     Node.Insert(root.left,value); 
    } 
    else 
     { 
     Node new_node = new Node(); 
     new_node.data = value; 
     root.left=new_node; 
    } 

} 
if(value > root.data) 
    { 
    if(root.right !=null) 
     { 
     Node.Insert(root.right,value); 
    } 
    else 
     { 
     Node new_node = new Node(); 
     new_node.data=value; 
     root.right=new_node; 
    } 

} 
return root; 
} 

Answer 2

Базовая реализация бинарного дерева ..hope это помогает вам

class Node { 

    Integer data; 

    Node left; 

    Node right; 

    Node(Integer data) { 

    this.data=data; 

    left=null; 

    right=null; 

    } 

} 

public class BinarySearchTree { 

    private Node root; 

    private Node searchElement; 

    public BinarySearchTree() { 

    root=null; 

} 

public void insert(Integer data) { 

    if(root==null) { 

     root=new Node(data); 

     System.out.println("root"); 

       }else { 

    root=insert(data,root); 

    } 

} 

public Node insert(Integer data,Node traverse) { 

    if(traverse==null){ 

     traverse=new Node(data); 

       } 

    else if(data<traverse.data){ 

     traverse.left=insert(data,traverse.left); 

      } 

    else { 

     traverse.right=insert(data,traverse.right); 

      } 

    return traverse; 

} 


public Node search(int element,Node traverse) { 

    if(traverse==null) { 

     System.out.println("Element not found"); 

     return traverse; 

    }else if(element<traverse.data) { 

     traverse.left=search(element,traverse.left); 

     return traverse; 

    }else if(element>traverse.data) { 

     traverse.right=search(element,traverse.right); 

     return traverse; 

    }else if(element==traverse.data) { 

     System.out.println("element found"); 

     System.out.println(traverse); 

     return traverse; 

    } 

    return traverse; 

} 

public void search(int element) { 

    searchElement=search(element,root); 

} 

public static void main(String... args){ 

    BinarySearchTree bst=new  BinarySearchTree(); 

    bst.insert(10); 

    bst.insert(12); 

    bst.insert(6); 

    bst.insert(100); 

    bst.search(12); 

} 

}