# Binary Search

Preorder to Binary Search Tree
---
- Preorder 한 결과가 있는 Array를 기반으로 Binary Search Tree 를 만들기 위한 방법은 무엇이 있을까? Binary Search 를 사용하면 가장 naive 한 방법으로 해결할 수 있다.
- Binary Search 는 정렬되어있는 Array가 주어질 때 어떤 값을 찾는 가장 기본적인 방법이다. 단순히 어떤 값을 찾을 때 뿐만 아니라 여기서는 다양한 용도로 활용될 수 있는 것 같다.
- 예를 들어, preorder 로 정렬된 Array 에서 왼쪽 파트와 오른쪽 파트를 구할 때 사용할 수 있다. 이게 가능한 이유는 preorder 라는 특성때문인 것으로 보인다. preorder 는 가장 먼저 보이는 순서대로 방문한다. 따라서 먼저 방문한 것이 부모이다. 그러면 binary search tree 를 만들기 위해서는 왼쪽과 오른쪽을 알아야 하는데, 여기서 가장 먼저 방문한 부모를 기준으로 왼쪽, 오른쪽 파트를 구해할 수 있다. 이 때 사용하는 것이 binary search 이다.
- 코드를 보면 아래와 같다.

def bstFromPreorder(A):
    if not A: return None

    root = TreeNode(val=A[0])
    import bisect 
    # binary search 를 통해서 
    # 특정값이 들어갈 인덱스를 반환
    i = bisect.bisect(A, A[0])
    root.left = self.bstFromPreorder(A[1:i])
    root.right = self.bstFromPreorder(A[i:])
    
    return root

- 이 방법의 시간 복잡도는 $O(N^2)$ 이다. 그 이유는 배열을 매번 복사해서 재귀함수를 호출하기 때문이다. 이를 해결하기 위해서 index 를 사용한 Binary Search를 할 수 있는데, 그 방법은 아래와 같다.

def helper(i, j):
    if i == j: return None
    root = TreeNode(A[i])
    mid = bisect.bisect(A, A[i], i + 1, j)
    root.left = helper(i + 1, mid)
    root.right = helper(mid, j)
    return root

return helper(0, len(A))

- 이 방법의 시간복잡도는 $O(NlogN)$ 이다. Binary Search 를 하는데 소요되는 시간은 $O(logN)$ 이고, 모든 노드에 대한 작업을 하기 때문에 $O(N)$을 곱할 수 있다.
- 이 문제에서 배울 수 있는 또 하나의 스킬은 bisect 를 사용하는 방법이다. bisect 는 binary search 를 통해서 특정 원소가 배열의 어디 인덱스에 위치할 수 있는지 알려주는 기능을 한다. 또한, 두번째 코드에서 봤던 것 처럼
- 문제: https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/