Binary Search Tree is a node-based binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

When we are talking about the average case, it is the time it takes for the operation on a balanced tree, and when we are talking about the worst case, it is the time it takes for the given operation on a non-balanced tree.

Time Complexity of Binary Search Tree

Operations	Worst Case	Average Case	Best Case
Insert	O(n)	O(log n)	O(1)
Delete	O(n)	O(log n)	O(1)
Search	O(n)	O(log n)	O(1)

The equation T(n)= T(n/2)+1 is known as the recurrence relation for binary search. 

To perform binary search time complexity analysis, we apply the Master Theorem to the equation and get O(log n).

Below are the basic steps to performing Binary Search.

1. Find the mid element of the whole array, as it would be the search key.
2. Look at whether or not the search key is equivalent to the item in the middle of the interval and return an index of that search key. 
3. If the value of the middle item in the interval is more than the search key, reduce the interval’s lower half.
4. If the opposite, then lower the upper half.
5. Repeat from point 2, until the value is found or the interval gets empty.

Applications of Binary tree:

1. Implementing routing table in router.                        
2. Data compression code                                                            
3. Implementation of Expression parsers and expression solvers              
4. To solve database problems such as indexing.                  
5. Expression evaluation                                                        
6. One of the most important application of binary trees is balanced binary search trees like Red-Black trees,AVL trees,Scapegoat trees.
7. Binary trees are used in Huffman coding, which are used as a compression code.
8. Binary trees are used in Binary search trees, which are useful for maintaining records of data without much extra space.
9. BST a kind of binary tree is used in Unix kernels for managing a set of virtual memory areas(VMAs).
10. Nearly all database (and database-like) programs use a binary tree to implement their indexing systems.

LeetCode 704 - Binary Search [easy]

Given an array of integers nums that is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

 

Example 1: Input: nums = [-1,0,3,5,9,12],  target = 9       Output: 4        Explanation: 9 exists in nums and its index is 4

Solution:                                                                                

class Solution:                                                                      
    def search(self, nums: List[int], target: int) -> int:            
        start = 0                                                                         
        end = len(nums)                                                            
        while start < end:                                                             
            mid = (end + start) // 2                                                 
            if nums[mid] == target:                                                   
                return mid                                                                   
            elif nums[mid] > target:                                                  
                end = mid                                                                   
            elif nums[mid] < target:                                                     
                start = mid + 1                                                              

        return -1                                                                               

Time Complexity: O(log n) where n is the total elements in the given array.  Space Complexity: O(1)

LeetCode 744. Find Smallest Letter Greater Than Target

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target. Note that the letters wrap around.

• For example, if target == 'z' and letters == ['a', 'b'], the answer is 'a'.

Example 1: Input: letters = ["c","f","j"],  target = "a"  Output: "c"

Solution:                                                                                  

class Solution:                                                                              
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        left, right = 0, len(letters)-1                                                  
        if target >= letters[right] or target < letters[left]:                   
            return letters[0]                                                              
        while left < right:                                                                 
            mid = (right + left) // 2                                                  
            if target < letters[mid]:                                                 
                right = mid                                                             
            else:                                                                         
                left = mid + 1                                                          
        return letters[right]