NeetCode 17번 알고리즘: Binary Search Tree

Alogrithm

 

Code

def search(root, target):
    if not root:
        return False
    
    if target > root.val:
        return search(root.right, target)
    elif target < root.val:
        return search(root.left, target)
    else:
        return True

Time Complexity

Balanced: O(logn)

Worst (skewed tree) : O(n)

 

Array Binary Search와 다른점

Search에서는 O(logn)으로 동일하지만 array와 다르게 insert와 delete가 매우 효율적임.