이진 탐색 트리(Binary Search Tree)

이와 같이 부모노드가 왼쪽 자신노드보다 크가 오른쪽 자식 노드보다 작은 이진 트리를 이진 탐색 트리라고 한다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    if (!root) return null;
    if (root.val == val) {
        return root;
    }
    if (root.val > val) {
        return searchBST(root.left, val);
    } else if (root.val < val) {
        return searchBST(root.right, val);
    }
    return null;
};

val 와 root 노드를 입력받아 자식 노드중 val와 값이 일치하는 노드가 있다면 그 노드를 root로 삼는 서브 트리를 반환하는 문제이다.
현재 탐색중인 노드의 값이 주어진 값보다 크다면 왼쪽 자식 노드로 재귀호출을 하고 현재 탐색중인 노드의 값이 주어진 값보다 작다면 오른쪽 자식 노드로 재귀호출을 한다.
그러다 값이 같은 노드를 찾는다면 그 노드를 반환하면 된다.
값을 찾지 못한경우에 null을 반환한다.