[Hackerrank] BinarySearchTreeInsertion

https://www.hackerrank.com/challenges/binary-search-tree-insertion/problem

Binary Search Tree : Insertion | HackerRank

package exam.complete;
//https://www.hackerrank.com/challenges/binary-search-tree-insertion/problem

import exam.Node;

public class BinarySearchTreeInsertion {
    public static void main(String[] args) {
        Node root = insert(null, 4);
        insert(root, 2);
        insert(root, 3);
        insert(root, 1);
        insert(root, 7);
        insert(root, 6);
    }
    public static Node insert(Node root, int data) {
        if(root == null) return new Node(data);
        insert(data, root);
        return root;
    }

    private static Node insert(int data, Node nowNode) {
        if(nowNode == null) return new Node(data);
        if(nowNode.val > data) nowNode.left = insert(data, nowNode.left);
        if(nowNode.val < data) nowNode.right = insert(data, nowNode.right);
        return nowNode;
    }
}

 

이진트리에 새로운 데이터를 적절한 위치에 넣을 수 있는 메소드 생성.

 

이진트리 

• 루트노드의 Left child는 루트노드 값보다 작아야 하고, Right child는 루트 노드의 값보다 커야한다.
• 루트 노드의 서브트리 또한 이 법칙을 지켜야 한다.
• 새로운 값을 넣을 때 루트 노드부터 recursive하게 탐색해나가면서 새로운 노드가 insert될 적절한 위치에 왔을 때(리프 노드), return 하여 트리를 완성시킨다.