You can always run a sequential search—scanning the array from the beginning to the end—on the array. But if the array is sorted, running the binary search algorithm is much more efficient.

Let's learn how binary search works, its time complexity, and code a simple implementation in Python.

How Does Linear Search Work?

We'll start our discussion with linear or sequential search.

Suppose we have an unsorted sequence of numbers nums. Given this nums array, you should check if the target is present in nums. You don’t have information about whether nums is sorted.

So the only way you can do this is to scan the array in a linear fashion, starting at the first element—until you find a match.

You can loop through the entire array to check if the element at index i matches the target. Once you find a match, you can break out of the loop.

Notice that in the worst case, you’ll have to scan the entire array and be lucky enough to find a match at the last index. Or you’ll have exhausted the array—without finding a match—indicating that the element is not present in the array.

Suppose the array has n elements. Because you have to scan the entire array—in the worst case—the linear search algorithm has a time complexity of O(n).

Here's an example:

Linear Search Example | Image by the author

But when you do not know anything about the sequence, this is the best you can do. So linear or sequential search is the best you can do when searching through unsorted sequences.

How Linear Search Works in Python

The function linear_search takes in an array nums and a target to search for. It then loops through the array sequentially to check if target is present in nums:

def linear_search(nums,target):
  for num in nums:
    if num == target:
      return True
  return False

Here are a couple of sample outputs:

nums = [14,21,27,30,36,2,5,7,11]
target = 27

print(linear_search(nums,target))
# Output: True

target = 100
print(linear_search(nums,target))
# Output: False

How Does Binary Search Work?

Now consider the nums sequence with n elements sorted in ascending order. For any valid index k, the following holds True for the element a_k at index k:

The elements at indices 0, 1, 2, …, (k-1) are all less than or equal to a_k. And all elements at indices (k+1) to (n-1) are greater than or equal to a_k.

With this information, you no longer need to run a linear scan. You can do it much faster with binary search.

We’re given a sorted array nums and a target. Let mid denote the middle-most index of the array and nums[mid] denote the element at the middle index. Here’s how the binary search algorithm works:

• Check if nums[mid] is equal to the target. If so, we’ve already found a match—in the very first step—and the search terminates.
• If nums[mid] > target, you only need to search the left half of the array. Even when you search through the left subarray you can use the same binary search algorithm.
• If nums[mid] < target, you can ignore all the elements up to the middle element and only consider the right half of the array.

Notice that we have a recurrence relation here. First, we start by running the binary search algorithm on the array with n elements. If we don't find the target in the very first step, we run binary search on the subarray of size at most n/2 elements.

If we end up with an empty array or an array with one element that is not the target, we conclude that the target does not exist in the nums array.

Binary Search Example | Image by the author

How to Implement Binary Search in Python

Here's a recursive implementation of binary search in Python:

def binary_search(nums,target,low,high):
  if low > high:
    return False
  else:
    mid = (low + high)//2
    if nums[mid] == target:
      return True
    elif nums[mid] < target:
      return binary_search(nums,target,mid+1,high)
    else:
      return binary_search(nums,target,low,mid-1)

With a few sample runs of the binary_search function:

nums = [2,5,7,11,14,21,27,30,36]
target = 27

print(binary_search(nums,target,0,len(nums)-1))
# Output: True

target = 38
print(binary_search(nums,target,0,len(nums)-1))
# Output: False

What Is the Time Complexity of Binary Search?

In binary search, we know that the search space is reduced by half at each step and this guides us in computing the time complexity.

For an array with n elements, we check if the middle-most element matches the target. If so, we return True and terminate the search.

But if the middle element does not match the target, we perform binary search on a subarray of size at most n/2. In the next step, we have to search through an array of size at most n/4. And we continue this recursively until we can make a decision in a constant time (when the subarray is empty).

At step k, we need to search through an array of size at most n/(2^k). And we need to find the smallest such k for which we have no subarray to search through.

Mathematically:

The time complexity of binary search is, therefore, O(logn). This is much more efficient than the linear time O(n), especially for large values of n.

For example, if the array has 1000 elements. 2^(10) = 1024. While the binary search algorithm will terminate in around 10 steps, linear search will take a thousand steps in the worst case.

Wrapping Up

And that's a wrap. I hope you found this introduction to binary search helpful! You’ll often run into questions involving binary search in coding interviews.

If you’re preparing for coding interviews, check out 10 Common Coding Interview Questions [Solved] on freeCodeCamp’s YouTube channel.

The algorithm is fast in searching for elements because it removes half of the array every time the search iteration happens.

So instead of searching through the whole array, the algorithm removes half of the array where the element to be searched for can't be found. It does this continuously until the element is found.

In a case where the element to be searched for doesn't exist, it returns a value of -1. If the element exists, then it returns the index of the element.

If the explanations above seem complex, then you should check out this visual guide on how the binary search algorithm works.

In this article, you'll see an implementation of the binary search algorithm in C++.

Let's get started!

Binary Search Algorithm Example in C++

In this section, we'll break down and explain the implementation of binary search in C++.

Here's the code:

#include <iostream>
using namespace std;

int binarySearch(int array[], int low, int high, int number_to_search_for) {

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (number_to_search_for == array[mid]){
            return mid;
        }

        if (number_to_search_for > array[mid]){
            low = mid + 1;
        }

        if (number_to_search_for < array[mid]){
            high = mid - 1;
        }

    }

  return -1;
}

int main(void) {
  int arrayOfNums[] = {2,4,7,9,10,13,20};

  int n = sizeof(arrayOfNums) / sizeof(arrayOfNums[0]);

  int result = binarySearch(arrayOfNums, 0, n - 1, 13);

  if (result == -1){
      printf("Element doesn't exist in the array");
  }
  else{
      printf("The index of the element is %d", result);
  }

  // The index of the element is 5
}

To start with, we created a method called binarySearch which had four parameters:

• array[] represents the array to be searched through.
• low represents the first element of the array.
• high represents the last element of the array.
• number_to_search_for represents the number to be searched for in array[].

Next, we created a while loop that will run continuously until the search operation returns a value – either the index of the element or -1.

In the while loop:

mid is used to represent the center/midpoint of the array: int mid = low + (high - low) / 2;.

The first if statement is executed if mid has the same value as the element to be searched for:

if (number_to_search_for == array[mid]){
    return mid;
}

The second if statement moves the position of low to the index after the midpoint of the array:

if (number_to_search_for > array[mid]){
    low = mid + 1;
}

This removes all the elements on the left side of the array because the element to be searched for is greater than they are, so there is no need to search through that part of the array.

The third if statement does the opposite of the second statement – it moves the position of high to the index before the midpoint of the array:

if (number_to_search_for < array[mid]){
    high = mid - 1;
}

Here's a summary of the code in the if statements:

1. If the number to be searched for is equal to mid, the mid index will be returned.
2. If the number to be searched for is greater than mid, search through the elements on the right side of mid.
3. If the number to be searched for is less than mid, search through the elements on the left side of mid.

If the number to be searched for doesn't exist, -1 will be returned. You can see this after the while loop in the code.

Lastly, we tested the binarySearch method:

int main(void) {
  int arrayOfNums[] = {2,4,7,9,10,13,20};

  int n = sizeof(arrayOfNums) / sizeof(arrayOfNums[0]);

  int result = binarySearch(arrayOfNums, 0, n - 1, 13);

  if (result == -1){
      printf("Element doesn't exist in the array");
  }
  else{
      printf("The index of the element is %d", result);
  }

  // The index of the element is 5
}

In the code above, we passed in the values of the parameters created in the binarySearch method: binarySearch(arrayOfNums, 0, n -1, 13).

• arrayOfNums represents the array to be searched for: {2,4,7,9,10,13,20}.
• 0 represents the first index of the array.
• n - 1 represents the last index of the array. Have a look at the code to see how n was created.
• 13 is the number to be searched for in arrayOfNums.

When you run the code, "The index of the element is 5" will be printed in the console. This is because the index of the number to be searched for (13) is 5.

You can play around with the code by changing the value of the number to be searched for.

Summary

In this article, we talked about the implementation of the binary search algorithm in C++.

We saw a code example that had a binarySearch method which took in parameters, searched through an array of numbers, and returned the appropriate value after the search operation.

We also saw a detailed explanation of each part of the code.

Happy coding!

The binary search algorithm is one of the commonly used algorithms in programming. It is used to search and find an element in a sorted array.

The binary search algorithm is different from the binary search tree. We'll talk about their differences later in this article.

In this article, you'll learn how the binary search algorithm works with the aid of diagrams and code examples.

You'll see how to implement the algorithm in your Java program.

How Does the Binary Search Algorithm Work?

In this section, you'll see a practical application of binary search using diagrams.

The binary search algorithm is a divide and conquer algorithm that searches for a specific element in a sorted array.

Note that the collection of elements/array must be sorted for the algorithm to work efficiently.

Here are the steps involved with the binary search algorithm:

Step #1 - Sort the Array

In order to start the search, you'll need to have a sorted array. The image above has a collection of numbers sorted in ascending order: 2,3,6,8,9,13,20.

Let's assume that the element we're looking for is 13. We'll store this in a variable called number_to_search_for.

Step #2 - Choose Low and High Values

sorted array with low and high pointers

The first index of the array will be denoted as low while the highest index will be denoted as high.

These values will help you get the midpoint of the array.

Midpoint = (low + high) / 2.

Step #3 - Choose Midpoint/Middle Element

sorted array with low, high, and middle pointers

The image above shows the midpoint which is at the center of the array.

Now that you know the low, high, and midpoint of the array, the binary search operation can begin.

Step #4 - Binary Search

This is what happens during the binary search:

1. If number_to_search_for is equal to midpoint, the midpoint index will be returned.
2. If number_to_search_for is greater than midpoint, search through the elements on the right side of the midpoint.
3. If number_to_search_for is less than midpoint, search through the elements on the left side midpoint.

Step 3 will only be relevant if step 2 is false. If number_to_search_for doesn't exist in the array, return -1.

Let's simplify the steps above using diagrams:

This is the array we're working with: 2,3,6,8,9,13,20.

number_to_search_for = 13.

midpoint = 8.

low = 2.

high = 20.

Iteration #1

From the steps listed above, you begin by comparing number_to_search_for to midpoint.

sorted array with low, high, and middle pointers

As you can see in the diagram above, the value of number_to_search_for and midpoint are not the same.

The next step is to find out if the number_to_search_for is greater than or less than midpoint.

In our own case, it is greater than midpoint so we'll focus on the elements on the right side of the midpoint — 9, 13, and 20.

This makes the search much faster because we've cut out half of the array that isn't needed.

We'll repeat all the steps for those elements as well.

The steps will run continuously until the element is found. In a case where the element doesn't exist, -1 will be returned.

Iteration #2

sorted array with low, high, and middle pointers

Comparing the midpoint and number_to_search_for in the diagram above, we have the same value.

At this point, the binary search operation stops because we've found the number. The index of the number will be returned.

That is: index 5 from the original array (2,3,6,8,9,13,20).

In the next section, you'll see how to implement the algorithm in Java.

Binary Search Algorithm Example in Java

class BinarySearch {
    private static int binarySearch(int numArray[], int number_to_search_for) {
        int low = 0;
        int high = numArray.length - 1;

        while (low <= high){
            int middleIndex = (low + high) / 2;
            int middleIndexNumber = numArray[middleIndex];

            if (number_to_search_for == middleIndexNumber){
                return middleIndex;
            }
            if (number_to_search_for < middleIndexNumber){
                high = middleIndex - 1;
            }
            if (number_to_search_for > middleIndexNumber){
                low = middleIndex + 1;
            }
        }

        return -1;
  }
    public static void main(String args[]) {

        int[] arrayofnums = {2,3,6,8,9,13,20};

        System.out.println(binarySearch(arrayofnums, 13));
        // 5

    }

}

In the code above, we created a method called binarySearch with two parameters — int numArray[] and int number_to_search_for:

private static int binarySearch(int numArray[], int number_to_search_for){...}

The first parameter represents the array to be searched through. The second represents the number to be searched for.

Next, we defined the low and high variables to represent the first and last index of the array:

int low = 0;
int high = numArray.length - 1;

After that, we created a while loop with if statements matching the 3 steps used in the previous section (Step #4 - Binary Search section):

while (low <= high){
    int middleIndex = (low + high) / 2;
    int middleIndexNumber = numArray[middleIndex];

    if (number_to_search_for == middleIndexNumber){
        return middleIndex;
    }
    if (number_to_search_for < middleIndexNumber){
        high = middleIndex - 1;
    }
    if (number_to_search_for > middleIndexNumber){
        low = middleIndex + 1;
    }
}

You can have a look at the Step #4 - Binary Search section to understand the code in the while loop.

We then returned -1 after the while loop in case the number being searched for doesn't exist in the array.

Lastly, we tested the method to be sure the functionality worked as expected:

public static void main(String args[]) {

     int[] arrayofnums = {2,3,6,8,9,13,20};

     System.out.println(binarySearch(arrayofnums, 13));
     // 5

}

We specified 13 as the second parameter and got index 5 returned.

If you use a number that doesn't exist in the array, you'll get -1 returned.

Differences Between Binary Search Algorithm and Binary Search Tree

Although both binary search algorithm and binary search tree are both used for searching, there are some differences in mode operation of operation and data structure.

Here are some differences:

• Binary search algorithm is used for searching while binary search tree is used for searching, insertion, and deletion.
• Binary search algorithm compares the middle element with the element being searched for while binary search tree compares the value of nodes in a tree.
• Binary search algorithm searches through an array or list while binary search tree traverses through a tree of nodes.

You can read more about the binary search tree here.

Summary

In this article, we talked about the binary search algorithm. It is to search for specific elements in an array.

We saw how the algorithm works using visual guides. Then we saw an implementation of the algorithm in Java.

Lastly, we saw the differences between binary search algorithm and binary search tree.

Happy coding!

When going through search results on the web, we pick the most relevant articles or resources that we think will help us.

Search is such a part of our lives because we cannot always have the answers. And there are various algorithms that help programs run more efficiently and deal with data more effectively.

What We'll Cover in This Tutorial

• What is a Search Algorithm?

• What is a Binary Search algorithm?

• How Binary Search Works – Divide and Conquer

• Processes involved in Binary Search Algorithms

• Methods Used in Binary Search Algorithms

• Real-life examples of Binary Search

What is a Search Algorithm?

A search algorithm works to retrieve items from any data structure. It compares the data that comes in as input to the information stored in its database and brings out the result. An example is finding your best friend’s number in your contact list of 1,000 numbers.

There are different types of search algorithms. Some of them are:

Linear search algorithms

Linear search algorithms are the simplest of all the search algorithms. As the name implies, they operate in a sequence.

Linear search checks elements in a list one after the other to find a particular key value. This key value is among other items in the list and the algorithm returns the position by going through the check.

Dijkstra's algorithm

Dijkstra's shortest path algorithm is used in more advanced searches. Dijkstra’s algorithm maps out the shortest distance between two nodes. These nodes are often route networks.

This type of search is useful when you're trying to find routes on maps. It gives you options based on finding the shortest path possible.

Binary Search Algorithm

Binary search algorithms are also known as half interval search. They return the position of a target value in a sorted list.

These algorithms use the “divide and conquer” technique to find the value's position.

Binary search algorithms and linear search algorithms are examples of simple search algorithms.

In binary search, the middle element in the list is found before comparing with the key value you are searching for. But in linear search, the elements are taken one by one in the list by looping through and comparing with the key value.

‌During Binary search, the list is split into two parts to get the middle element: there is the left side, the middle element, and the right side.

The left side contains values smaller than the middle element and the right side contains values that are greater than the middle element. This method uses a sorted list to work.

A sorted list has its items arranged in a particular order. To make search efficient for binary search, the values in the list have to be arranged in the right order to satisfy the process of search. If a list has its values mixed up, it has to be sorted by a sorting algorithm before you perform the search.

Sorting algorithms

Sorting algorithms accept an unsorted list as an input and return a list with the elements arranged in a particular order (mostly ascending order).

There are different types of sorting algorithms, like insertion sort, quick sort, bubble sort, and merge sort.

How Binary Search Works – Divide and Conquer

A binary search algorithm uses a technique called “divide and conquer” to tackle its task. The merge sort algorithm employs the same technique to sort items in a list.

In binary search algorithms, the “divide and conquer” method works this way:

• The algorithm splits the list into two parts: the left side and right side, separated by the middle element

• It creates a variable to store the value of the item to be searched for

• It picks out the middle element and compares it with the item to be searched

• If the items compared are equal, then process ends

• If not, the middle element is either greater or lesser than the item you're searching for. If the middle element is greater, the algorithm splits the list and searches for the element on the left side. If the middle element is smaller, it splits the list and searches for the element on the right side of the list.

You can implement this method using recursion or iteration in the binary search process.

How the Binary Search Algorithm Works – Step by Step

First, before performing the search, you need to sort the list.

Then you create a variable that stores the value to be searched for.

Next, the list is divided into two parts. We sum up the first and last indexes to find the index of the middle element in the list.

When the calculated value of the middle element index is a float (like 3.45), we take the whole part as the index.

Then we compare the value we're searching for and the middle element.

Binary Search Use Case

Condition 1

If the middle element is equal to the value to be searched, the position where the value is will be returned and the process is terminated.

if middle element == to_search 
    return position of middle element 
*code ends*

Using the Image above as an example:

The middle element = 23, the target value/to_search = 23. Comparing the two values, we see that they are equal on both sides. 23 appears at index 2 in the list. That is the output of the code and the process ends.

Condition 2

If the middle element is not equal to "to_search", then we check the following scenarios:

Scenario 1: if the middle element is greater than the value to be searched:

if middle element > to_search

• the search moves to the left side because the values are less than the middle element

• the position of the middle element shifts to the left by 1

• new_position = index(middle element) - 1

• a new search begins and the search ends at that new position and it takes all the values before it.

Using the image above as an example:

middle element = 23
to_search = 4
if 23 > 4

• we move to the left side because all numbers less than 23 are stored there. index (23) = 2

• new_position = index(23) - 1 = 2-1 = 1

• The search will end at index 1 and take all other value(s) before index 1

Comparing the new middle element (4) to the target value (4), we see they are equal. So the search is terminated and the output is the position "4" occupies in the list (which is index 0).

Scenario 2: if the middle element is less than the value to be searched:

if middle element < to_search

• the search moves to the right side because the values are greater than the middle element

• the position of the middle element shifts to the right by 1

• new_position = index(middle element) + 1

• a new search begins at the new position and ends at the last index in the list

• all values are taken from the new position to the end of the list

Using the first Image as an example:

middle element = 23 
to_search = 32 
if 23 > 32

• we move to the right side because all numbers greater than 23 are stored there. index(23) = 2 ,

• new_position = index(23) + 1 = 2+1 = 3

• The search will begin at index 3 and take all other value(s) after index 3

Comparing the middle element (32) to the target value (32), we see they are equal. So the search is terminated and the output is the position "4" occupies in the list (index 4).

‌‌Methods Used in Binary Search Algorithms

There are two methods that can implement the “divide and conquer” technique in the search. They are iteration and recursion.

What is Iteration?

In order to get elements from a tuple, list, or dictionary, you iterate through the items with loops.

Iteration is a repeated sequence of statements during execution and it has a countable number of values. For example, when looping through random lists, we loop through the actual variable containing the lists to get the values.

Code implementation for binary search with iteration

Here's the code:

def binary_search(list_num , to_search):
    first_index = 0
    size = len(list_num)
    last_index = size - 1
    mid_index = (first_index + last_index) // 2
    # print(mid_index)
    mid_element = list_num[mid_index]
    # print(mid_element)

    is_found = True
    while is_found:
        if first_index == last_index:
            if mid_element != to_search:
                is_found = False
                return " Does not appear in the list"

        elif mid_element == to_search:
            return f"{mid_element} occurs in position {mid_index}"

        elif mid_element > to_search:
            new_position = mid_index - 1
            last_index = new_position
            mid_index = (first_index + last_index) // 2
            mid_element = list_num[mid_index]
            if mid_element == to_search:
                return f"{mid_element} occurs in position {mid_index}"

        elif mid_element < to_search:
            new_position = mid_index + 1
            first_index = new_position
            last_index = size - 1
            mid_index = (first_index + last_index) // 2
            mid_element = list_num[mid_index]
            if mid_element == to_search:
                return f"{mid_element} occurs in position {mid_index}"



list_container = [16 , 18 , 20 , 50 , 60 , 81 , 84 , 89]
print(binary_search(list_container , 81))
print(binary_search(list_container , 10))

Now let's see what's going on here:

• First, we pass in a list and a value to be searched (to_search) as an input to a function.

• In the function, we create a variable name of first index and assign it to "0". The first index in a list is always "0".

• Then we create four variable names: "size" to store the length of the list, "last_index" to store the index of the last element, "mid_index" to store the operation of finding the middle element index, and "mid_element" to store the middle element gotten from the list using the mid index as position.

• Afterwards, we introduce a while loop to make the conditions run on repeat. Above the while loop we create a variable name "is_found" and set it to "True". This condition checks if the "item to be searched" is found or not.

• In the while loop, we check all the conditions. The first condition is to check if the middle element and the variable "to_search" are equal. If they are equal, the position of the item will be returned.

• Then we check for the second condition (if middle element != item to be searched) which leads us to the two scenarios:
  – if the middle element is greater than the item to be searched, the new position will shift to the left once. The search will begin from the first index and end at the new position which is the new last index.
  – If the middle element is less than the item to be searched, the new position will shift to the right once. The search will begin from the new position as the new first index and end at the last index.

At the end of these scenarios, we check if the new middle element is the same as the item to be searched. If it is the same, the position of the item will be returned. If not, the conditions are checked until the values are equal.

For error handling, let's say we want to search for a value that does not appear in the list. If we end at the two conditions, the loop will keep running and may eventually crash the system.

To catch the error, we set a condition to check if the first index equals the last index. Then we check if the middle element is equal to the item to be searched. If it is not equal," is found" will be "False". When you run this, it shows an empty array. In my code, the output is a statement.

The final step is to call the function and the result is displayed.

And here are the results:

If the element is in the list, the output is the position.

If the element is not in the list, the output is a statement like this:

What is ‌‌Recursion?

A function is said to be recursive if it makes reference to itself or previous term(s) to solve a task.

A recursive function is repetitive and it is executed in sequence. It starts from a complex problem and breaks things down into a simpler form.

Code implementation for binary search with recursion

With recursion, it is a bit simpler and requires less code. Here's what it looks like:

def binary_search(list_num, first_index, last_index, to_search):
    if last_index >= first_index:

        mid_index = (first_index + last_index) // 2
        mid_element = list_num[mid_index]


        if mid_element == to_search:
            return f"{mid_element} occurs in position {mid_index}"

        elif mid_element > to_search:
            new_position = mid_index - 1
            # new last index is the new position
            return binary_search(list_num, first_index, new_position, to_search)

        elif mid_element < to_search:
            new_position = mid_index + 1
             # new first index is the new position
            return binary_search(list_num, new_position, last_index, to_search)

    else:
        return " Does not appear in the list"

list_container = [ 1, 9, 11, 21, 34, 54, 67, 90 ]
search = 34
first = 0
last= len(list_container) - 1

print(binary_search(list_container,first,last,search))

• First, a function accepts four inputs: the first index, last index, list, and to_search (item to be searched).

• Then we check if the value of the last index is greater than or equal to the value of the first index. If the condition is true, we assign the operation of finding the middle element index to the variable name "mid_index". Then the middle element is gotten from the list using the mid index as position.

• We create an "if" statement under the first "if" block to check if the middle element and the variable "to_search" are equal. If they are equal, the position of the item will be returned.

• Then we check for the second condition, (if middle element != item to be searched) which leads us to two scenarios:
  – if the middle element is greater than the item to be searched, the new position will shift to the left once. The search will begin from the first index and end at the new position. We return the function and pass in the new position as the last index value.
  – if the middle element is less than the item to be searched, the new position will shift to the right once. The search will begin from the new position and end at the last index. We return the function and pass in the new position as the first index value.

• The last condition will be on the same indent as the first "if" statement. If the to_search is not in the list, it will return a statement

The final step is to call the function and the result is displayed.

And here are the results:

If the element is in the list, the output is the position:

If the element is not in the list, the output is a statement:

Real-life Examples of Binary Search‌

You might not realize it, but we perform binary search all the time. Here are a few examples of how you might use or encounter it in your daily life or work:

• Searching for a word in a dictionary

• searching for a literature text book in a literature section in a library

• searching for an element in a sorted list

• searching for students taller than 5 feet 3 inches in a line of students arranged according to their heights.

Conclusion

At the end of this article, you should be familiar with how binary search algorithms work and how to implement them in code.

It's fine if you could not grasp everything at once – just give yourself some time and practice. If you encounter any errors or have questions, you can reach out to me on Twitter.

‌‌

‌‌

‌‌

‌‌

‌‌

‌‌

‌

We will also see how to traverse a tree using some of the common algorithms – all illustrated with clear examples.

What Is a Binary Search Tree?

A binary search tree is a binary tree made up of nodes. Each node has a key signifying its value.

The value of the nodes on the left subtree are smaller than the value of the root node. And the value of the nodes on the right subtree are larger than the value of the root node.

The root node is the parent node of both subtrees.

The diagram below shows the main parts of a binary tree:

Diagram of a binary search tree

Let's us look at the relationship between the nodes.

• **A** is the root node.
• The left subtree begins at B while the right subtree begins at C.
• Node A has two child nodes – B and C.
• Node C is the parent node to F and G. F and G are siblings.
• Node F and G are know as leaf nodes because they do not have children.
• Node B is the parent node to D and E.
• Node D is the parent node to H and I.
• D and E are siblings as well as H and I.
• Node E is a leaf node.

So here are some important terms that we just used to describe the tree above:

Root: The topmost node in the tree.

Parent: A node with a child or children.

Child: A node extended from another node (parent node).

Leaf: A node without a child.

What Is a Binary Search Tree Used For?

Binary search trees help us speed up our binary search as we are able to find items faster.

We can use the binary search tree for the addition and deletion of items in a tree.

We can also represent data in a ranked order using a binary tree. And in some cases, it can be used as a chart to represent a collection of information.

Next, we'll look at some techniques used in traversing a binary tree.

What is Tree Traversal?

Traversing a tree means visiting and outputting the value of each node in a particular order. In this tutorial, we will use the Inorder, Preorder, and Post order tree traversal methods.

The major importance of tree traversal is that there are multiple ways of carrying out traversal operations unlike linear data structures like arrays, bitmaps, matrices where traversal is done in a linear order.

Each of these methods of traversing a tree have a particular order they follow:

• For Inorder, you traverse from the left subtree to the root then to the right subtree.
• For Preorder, you traverse from the root to the left subtree then to the right subtree.
• For Post order, you traverse from the left subtree to the right subtree then to the root.

Here is another way of representing the information above:

Inorder => Left, Root, Right.

Preorder => Root, Left, Right.

Post order => Left, Right, Root.

How to Traverse a Tree Using Inorder Traversal

We are going to create a tree similar to the one in the last section, but this time the node keys will be numbers instead of letters.

Remember that the values of the nodes on the left subtree are always smaller than the value of the root node. Also, the values of the nodes on the right subtree are larger than the value of the root node.

Here is the diagram we will be working with:

Recall that the order for inorder traversal is Left, Root, Right.

This is the result we get after using inorder traversal:

D, B, E, A, F, C, G

If that seems a bit complex for you to understand, then follow the order of the colors in the picture below

Inorder traversal

How to Traverse a Tree Using Preorder Traversal

The order here is Root, Left, Right.

Using the same diagram above, we have:

A, B, D, E, C, F, G

Here is the same diagram with different colors used as a guide:

Preorder traversal

How to Traverse a Tree Using Postorder Traversal

The order for post order traversal is Left, Right, Root.

Here is the output:

D, E, B, F, G, C, A

If you can't figure out how we arrived at that result, then use the colors in the picture below as a guide:

Postorder traversal

Conclusion

In this tutorial, we learned the basics of what a binary search tree is, what the various parts of a binary tree are, and the common terms associated with a tree. We also saw some of the algorithms we can use to traverse a tree.

Thank you for reading!

In this article, we'll learn how search algorithms work by looking at their implementations in Java and Python.

What is a Search Algorithm?

According to Wikipedia, a search algorithm is:

Any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values.

Search algorithms are designed to check or retrieve an element from any data structure where that element is being stored. They search for a target (key) in the search space.

Types of Search Algorithms

In this post, we are going to discuss two important types of search algorithms:

1. Linear or Sequential Search

2. Binary Search

Let's discuss these two in detail with examples, code implementations, and time complexity analysis.

Linear or Sequential Search

This algorithm works by sequentially iterating through the whole array or list from one end until the target element is found. If the element is found, it returns its index, else -1.

Now let's look at an example and try to understand how it works:

arr = [2, 12, 15, 11, 7, 19, 45]

Suppose the target element we want to search is 7.

Approach for Linear or Sequential Search

• Start with index 0 and compare each element with the target

• If the target is found to be equal to the element, return its index

• If the target is not found, return -1

Code Implementation

Let's now look at how we'd implement this type of search algorithm in a couple different programming languages.

Linear or Sequential Search in Java

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}

Linear or Sequential Search in Python

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

if __name__ == '__main__':
    nums = [2, 12, 15, 11, 7, 19, 45]
    target = 7
    print(search(nums, target))

Time Complexity Analysis

The Best Case occurs when the target element is the first element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1).

The Average Case: On average, the target element will be somewhere in the middle of the array. The number of comparisons, in this case, will be N/2. So, the time complexity will be O(N) (the constant being ignored).

The Worst Case occurs when the target element is the last element in the array or not in the array. In this case, we have to traverse the entire array, and so the number of comparisons will be N. So, the time complexity will be O(N).

Binary Search

This type of searching algorithm is used to find the position of a specific value contained in a sorted array. The binary search algorithm works on the principle of divide and conquer and it is considered the best searching algorithm because it's faster to run.

Now let's take a sorted array as an example and try to understand how it works:

arr = [2, 12, 15, 17, 27, 29, 45]

Suppose the target element to be searched is 17.

Approach for Binary Search

• Compare the target element with the middle element of the array.

• If the target element is greater than the middle element, then the search continues in the right half.

• Else if the target element is less than the middle value, the search continues in the left half.

• This process is repeated until the middle element is equal to the target element, or the target element is not in the array

• If the target element is found, its index is returned, else -1 is returned.

Code Implementation

Binary Search in Java

package algorithms.searching;

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 17, 27, 29, 45};
        int target = 17;
        System.out.println(search(nums, target));
    }

    static int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > target)
                end = mid - 1;
            else if (nums[mid] < target)
                start = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

Binary Search in Python

def search(nums, target):
    start = 0
    end = len(nums)-1

    while start <= end:
        mid = start + (end-start)//2


        if nums[mid] > target:
            end = mid-1
        elif nums[mid] < target:
            start = mid+1
        else:
            return mid

    return -1


if __name__ == '__main__':
    nums = [2, 12, 15, 17, 27, 29, 45]
    target = 17
    print(search(nums, target))

Time Complexity Analysis

The Best Case occurs when the target element is the middle element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1).

The Average Case: On average, the target element will be somewhere in the array. So, the time complexity will be O(logN).

The Worst Case occurs when the target element is not in the list or it is away from the middle element. So, the time complexity will be O(logN).

How to Calculate Time Complexity:

Let's say the iteration in Binary Search terminates after k iterations.

At each iteration, the array is divided by half. So let’s say the length of array at any iteration is N.

At Iteration 1,

Length of array = N

At Iteration 2,

Length of array = N/2

At Iteration 3,

Length of array = (N/2)/2 = N/2^2

At Iteration k,

Length of array = N/2^k

Also, we know that after k divisions, the length of the array becomes 1: Length of array = N⁄₂^k = 1\=> N = 2^k

If we apply a log function on both sides: log₂ (N) = log₂ (2^k)\=> log₂ (N) = k log₂ (2)

As (log_a (a) = 1)
Therefore,=> k = log₂ (N)

So now we can see why the time complexity of Binary Search is log₂ (N).

You can also visualize the above two algorithms using the simple tool built by Dipesh Patil - Algorithms Visualizer.

Order-agnostic Binary Search

Suppose, we have to find a target element in a sorted array. We know that the array is sorted, but we don’t know if it’s sorted in ascending or descending order.

Approach for Order-agnostic Binary Search

The implementation is similar to binary search except that we need to identify whether the array is sorted in ascending order or descending order. This then lets us make the decision about whether to continue the search in the left half of the array or the right half of the array.

• We first compare the target with the middle element

• If the array is sorted in ascending order and the target is less than the middle element OR the array is sorted in descending order and the target is greater than the middle element, then we continue the search in the lower half of the array by setting end=mid-1.

• Otherwise, we perform the search in the upper half of the array by setting start=mid+1

The only thing we need to do is to figure out whether the array is sorted in ascending order or descending order. We can easily find this by comparing the first and last elements of the array.

if arr[0] < arr[arr.length-1]
    array is sorted in ascending order 
else
    array is sorted in descending order

Code Implementation

Order-agnostic Binary Search in Java

package algorithms.searching;

public class OrderAgnosticBinarySearch {
    public static void main(String[] args) {
        int[] nums1 = {-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99};
        int[] nums2 = {99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1};
        int target = -1;
        System.out.println(search(nums1, target));
        System.out.println(search(nums2, target));
    }

    static int search(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        boolean isAscending = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target == arr[mid])
                return mid;

            if (isAscending) {
                if (target < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (target < arr[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }


}

Order-agnostic Binary Search in Python

def search(nums, target):
    start = 0
    end = len(nums)-1

    is_ascending = nums[start] < nums[end]

    while start <= end:
        mid = start + (end-start)//2

        if target == nums[mid]:
            return mid

        if is_ascending:
            if target < nums[mid]:
                end = mid-1
            else:
                start = mid+1
        else:
            if target < nums[mid]:
                start = mid+1
            else:
                end = mid-1

    return -1


if __name__ == '__main__':
    nums1 = [-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99]
    nums2 = [99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1]
    target = -1
    print(search(nums1, target))
    print(search(nums2, target))

Time Complexity Analysis

There will be no change in the time complexity, so it will be the same as Binary Search.

Conclusion

In this article, we discussed two of the most important search algorithms along with their code implementations in Python and Java. We also looked at their time complexity analysis.

Thanks for reading!

Subscribe to my newsletter

In this article, I will try my best to explain some core algorithms you should learn before a coding interview.

If you are not familiar with the concept of a binary tree, I encourage you to check out the wikipedia page. If you fully master those basic algorithms, you will have an easier time solving more complex problems.

What is a Binary Search Tree (BST)?

Commonly found in coding interviews, BST is a tree-like data structure with a single root at the very top. They are a great way to store numeric values as their ordered nature allows for fast search and lookups.

Compared to a normal tree, BST has the following properties:

• every left child has a smaller value than its parent
• every right child has a larger value than its parent
• every node can contain from 0 to 2 children.

The following diagram should clarify things a bit more.

Definition of a Binary Tree Node

A binary search tree

We usually define a Binary Tree Node with the following function in Javascript:

 function TreeNode(val, left, right) {
     this.val = val
     this.left = left
     this.right = right
 }

Binary Tree Basic Traversals (Inorder, Postorder, Preorder)

The first thing to know is how to loop through each node of the BST. This allows us to perform a function on all nodes of our BST. For example, if we want to find a value x in our BST, we'd need the nodes.

There are three main ways of doing this. Luckily, they share common themes.

Inorder traversal

A recursive algorithm is the easiest way to get started with binary tree inorder traversal. The idea is as follows:

• If the node is null, do nothing – else, recursively call the function on the node's left child.
• Then, do some operation on the node after traversing though all left children. Our current node is guaranteed to be the leftest node.
• Finally, call the function on node.right.

The Inorder algorithm traverses the tree nodes from left, to mid, to right.

/**
* @param {TreeNode} root
*/
const inorder = (root) => {
    const nodes = []
    if (root) {
        inorder(root.left)
        nodes.push(root.val)
        inorder(root.right)
    }
    return nodes
}
// for our example tree, this returns [1,2,3,4,5,6]

Postorder traversal

A recursive algorithm is the easiest way to get started with the postorder traversal.

• If the node is null, do nothing – else, recursively call the function on the node's left child.
• When there are no more left children, call the function on node.right.
• Finally, do some operation on the node.

Postorder traversal visits the tree nodes from left, to right, to mid.

/**
* @param {TreeNode} root
*/
const postorder = (root) => {
    const nodes = []
    if (root) {
        postorder(root.left)
        postorder(root.right)
        nodes.push(root.val)
    }
    return nodes
}
// for our example tree, this returns [1,3,2,6,5,4]

Preorder traversal

A recursive algorithm is the easiest way to get started with the preorder traversal.

• If the node is null, do nothing – else, do some operation on the node.
• Traverse to the left child of the node and repeat.
• Traverse to the right child of node and repeat.

Postorder traversal visits the tree nodes from mid, to left, to right.

/**
* @param {TreeNode} root
*/
const preorder = (root) => {
    const nodes = []
    if (root) {
        nodes.push(root.val)
        preorder(root.left)
        preorder(root.right)
    }
    return nodes
}
// for our example tree, this returns [4,2,1,3,5,6]

What is a Valid Binary Search Tree?

A valid binary search tree (BST) has ALL left children with values less than the parent node, and ALL right children with values greater than the parent node.

To verify if a tree is a valid binary search tree:

• Define the min and max value the current node can have
• If a node's value is not within those bounds, return false
• Recursively validate the node's left children, with the max bound set to the node's value
• Recursively validate the node's right children, with the min bound set to the node's value

/**
* @param {TreeNode} root
*/
const isValidBST = (root) => {
    const helper = (node, min, max) => {
        if (!node) return true
        if (node.val <= min || node.val >= max) return false
        return helper(node.left, min, node.val) && helper(node.right, node.val, max)
    }
    return helper(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
}

How to Find Binary Tree Max Depth

Here, the algorithm is attempting to find the height/depth of our BST. In other words, we are looking at how many 'levels' a BST contains.

• If the node is null, we return 0 as it does not add any depth
• Else we add + 1 to our current depth (we traversed one level)
• Recursively calculate the depth of node's children and return the maximum sum between node.left and node.right

/**
* @param {TreeNode} root
*/
const maxDepth = function(root) {
    const calc = (node) => {
        if (!node) return 0
        return Math.max(1 + calc(node.left), 1 + calc(node.right))
    }
    return calc(root)
};

How to Find the Lowest Common Ancestor Between Two Tree Nodes

Let's bump up the difficulty. How do we find the common ancestor between two tree nodes in our binary tree? Let's look at some examples.

A binary search tree

In this tree, the lowest common ancestor of 3 and 1 is 2. The LCA of 3 and 2 is 2. The LCA of 6 and 1 and 6 is 4.

See the pattern here? The LCA between two tree nodes is either one of the nodes itself (the case of 3 and 2), or a parent node where the first child is found somewhere in its left subtree, and the second child somewhere in its right subtree.

The algorithm to find the lowest common ancestor (LCA) between two tree nodes p and q is as follows:

• Verify if p or q is found in the left subtree or right subtree
• Then, verify if the current node is p or q
• If one of p or q is found in the left or right subtree, and one of p or q is the node itself, we have found the LCA
• If both p and q are found in the the left or right subtree, we have found the LCA

/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
*/
const lowestCommonAncestor = function(root, p, q) {
    let lca = null
    const isCommonPath = (node) => {
        if (!node) return false
        var isLeft = isCommonPath(node.left)
        var isRight = isCommonPath(node.right)
        var isMid = node == p || node == q
        if (isMid && isLeft || isMid && isRight || isLeft && isRight) {
            lca = node
        }
        return isLeft || isRight || isMid
    }
    isCommonPath(root)
    return lca
};

Wrapping Up

In summary, we have learned how to traverse, verify, and calculate the depth of a BST.

These algorithms are often asked about in coding interviews. It is important to understand them before practicing more advanced BST applications, like finding the LCA of two nodes.

Suppose you are given a list or an array of items. You are searching for a particular item. How do you do that?

Find the number 13 in the given list.

You just look at the list and there it is!

Now, how do you tell a computer to find it?

A computer cannot look at more than the value at a given instant of time. So it takes one item from the array and checks if it is the same as what you are looking for.

The first item did not match. So move onto the next one.

And so on…

This is done till a match is found or until all the items have been checked.

In this algorithm, you can stop when the item is found and then there is no need to look further.

So how long would it take to do the linear search operation? In the best case, you could get lucky and the item you are looking at maybe at the first position in the array!

But in the worst case, you would have to look at each and every item before you find the item at the last place or before you realize that the item is not in the array.

The complexity of linear search is therefore O(n).

If the element to be searched lived on the the first memory block then the complexity would be: O(1).

The code for a linear search function in JavaScript is shown below. This function returns the position of the item we are looking for in the array. If the item is not present in the array, the function will return null.

Example in Javascript

function linearSearch(arr, item) {
  // Go through all the elements of arr to look for item.
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] === item) { // Found it!
      return i;
    }
  }

  // Item not found in the array.
  return null;
}

Example in Ruby

def linear_search(target, array)
  counter = 0

  while counter < array.length
    if array[counter] == target
      return counter
    else
      counter += 1
    end
  end
  return nil
end

Example in C++

int linear_search(int arr[],int n,int num)
{
    for(int i=0;i<n;i++){
        if(arr[i]==num)
            return i;
   }
   // Item not found in the array
   return -1; 
}

Example in Python

def linear_search(array, num):
    for i in range(len(array)):
        if (array[i]==num):
            return i
    return -1

Global Linear Search

What if you are searching the multiple occurrences of an element? For example you want to see how many 5’s are in an array.

Target = 5

Array = [ 1, 2, 3, 4, 5, 6, 5, 7, 8, 9, 5]

This array has 3 occurrences of 5s and we want to return the indexes (where they are in the array) of all of them.

This is called global linear search and you will need to adjust your code to return an array of the index points at which it finds your target element.

When you find an index element that matches your target, the index point (counter) will be added in the results array. If it doesn’t match, the code will continue to move on to the next element in the array by adding 1 to the counter.

def global_linear_search(target, array)
  counter = 0
  results = []

  while counter < array.length
    if array[counter] == target
      results << counter
      counter += 1
    else
      counter += 1
    end
  end

  if results.empty?
    return nil
  else
    return results
  end
end

Why linear search is not efficient

There is no doubt that linear search is simple. But because it compares each element one by one, it is time consuming and therefore not very efficient. If we have to find a number from, say, 1,000,000 numbers and that number is at the last position, a linear search technique would become quite tedious.

So you should also learn about bubble sort, quick sort and other more efficient algorithms.

Other search algorithms:

• How to implement quick sort
• Binary search algorithm
• Jump search algorithm
• Search algorithms explained with examples
• Implement a binary search algorithm in Java without recursion
• More info on search algorithms

A BST is a data structure composed of nodes. It has the following guarantees:

1. Each tree has a root node (at the top).
2. The root node has zero or more child nodes.
3. Each child node has zero or more child nodes, and so on.
4. Each node has up to two children.
5. For each node, its left descendants are less than the current node, which is less than the right descendants.

AVL trees have an additional guarantee:

1. The difference between the depth of right and left subtrees cannot be more than one.

In order to maintain this guarantee, implementations of AVL trees include an algorithm to rebalance the tree when adding an additional element would cause the difference in depth between the right and left trees to be greater than one.

AVL trees have a worst case lookup, insert and delete time of O(log n).

Right Rotation

_Source: https://github.com/HebleV/valet_parking/tree/master/images_

Left Rotation

_Source: https://github.com/HebleV/valet_parking/tree/master/images_

AVL Insertion Process

This works similarly to a normal binary search tree insertion. After the insertion, you fix the AVL property by using left or right rotations.

• If there is an imbalance in left child of right subtree, then you perform a left-right rotation.
• If there is an imbalance in left child of left subtree, then you perform a right rotation.
• If there is an imbalance in right child of right subtree, then you perform a left rotation.
• If there is an imbalance in right child of left subtree, then you perform a right-left rotation.

Example

Here's an example of an AVL tree in Python:

class node:
    def __init__(self,value=None):
        self.value=value
        self.left_child=None
        self.right_child=None
        self.parent=None # pointer to parent node in tree
        self.height=1 # height of node in tree (max dist. to leaf) NEW FOR AVL

class AVLTree:
    def __init__(self):
        self.root=None

    def __repr__(self):
        if self.root==None: return ''
        content='\n' # to hold final string
        cur_nodes=[self.root] # all nodes at current level
        cur_height=self.root.height # height of nodes at current level
        sep=' '*(2**(cur_height-1)) # variable sized separator between elements
        while True:
            cur_height+=-1 # decrement current height
            if len(cur_nodes)==0: break
            cur_row=' '
            next_row=''
            next_nodes=[]

            if all(n is None for n in cur_nodes):
                break

            for n in cur_nodes:

                if n==None:
                    cur_row+='   '+sep
                    next_row+='   '+sep
                    next_nodes.extend([None,None])
                    continue

                if n.value!=None:       
                    buf=' '*int((5-len(str(n.value)))/2)
                    cur_row+='%s%s%s'%(buf,str(n.value),buf)+sep
                else:
                    cur_row+=' '*5+sep

                if n.left_child!=None:  
                    next_nodes.append(n.left_child)
                    next_row+=' /'+sep
                else:
                    next_row+='  '+sep
                    next_nodes.append(None)

                if n.right_child!=None: 
                    next_nodes.append(n.right_child)
                    next_row+='\ '+sep
                else:
                    next_row+='  '+sep
                    next_nodes.append(None)

            content+=(cur_height*'   '+cur_row+'\n'+cur_height*'   '+next_row+'\n')
            cur_nodes=next_nodes
            sep=' '*int(len(sep)/2) # cut separator size in half
        return content

    def insert(self,value):
        if self.root==None:
            self.root=node(value)
        else:
            self._insert(value,self.root)

    def _insert(self,value,cur_node):
        if value<cur_node.value:
            if cur_node.left_child==None:
                cur_node.left_child=node(value)
                cur_node.left_child.parent=cur_node # set parent
                self._inspect_insertion(cur_node.left_child)
            else:
                self._insert(value,cur_node.left_child)
        elif value>cur_node.value:
            if cur_node.right_child==None:
                cur_node.right_child=node(value)
                cur_node.right_child.parent=cur_node # set parent
                self._inspect_insertion(cur_node.right_child)
            else:
                self._insert(value,cur_node.right_child)
        else:
            print("Value already in tree!")

    def print_tree(self):
        if self.root!=None:
            self._print_tree(self.root)

    def _print_tree(self,cur_node):
        if cur_node!=None:
            self._print_tree(cur_node.left_child)
            print ('%s, h=%d'%(str(cur_node.value),cur_node.height))
            self._print_tree(cur_node.right_child)

    def height(self):
        if self.root!=None:
            return self._height(self.root,0)
        else:
            return 0

    def _height(self,cur_node,cur_height):
        if cur_node==None: return cur_height
        left_height=self._height(cur_node.left_child,cur_height+1)
        right_height=self._height(cur_node.right_child,cur_height+1)
        return max(left_height,right_height)

    def find(self,value):
        if self.root!=None:
            return self._find(value,self.root)
        else:
            return None

    def _find(self,value,cur_node):
        if value==cur_node.value:
            return cur_node
        elif value<cur_node.value and cur_node.left_child!=None:
            return self._find(value,cur_node.left_child)
        elif value>cur_node.value and cur_node.right_child!=None:
            return self._find(value,cur_node.right_child)

    def delete_value(self,value):
        return self.delete_node(self.find(value))

    def delete_node(self,node):

        ## -----
        # Improvements since prior lesson

        # Protect against deleting a node not found in the tree
        if node==None or self.find(node.value)==None:
            print("Node to be deleted not found in the tree!")
            return None 
        ## -----

        # returns the node with min value in tree rooted at input node
        def min_value_node(n):
            current=n
            while current.left_child!=None:
                current=current.left_child
            return current

        # returns the number of children for the specified node
        def num_children(n):
            num_children=0
            if n.left_child!=None: num_children+=1
            if n.right_child!=None: num_children+=1
            return num_children

        # get the parent of the node to be deleted
        node_parent=node.parent

        # get the number of children of the node to be deleted
        node_children=num_children(node)

        # break operation into different cases based on the
        # structure of the tree & node to be deleted

        # CASE 1 (node has no children)
        if node_children==0:

            if node_parent!=None:
                # remove reference to the node from the parent
                if node_parent.left_child==node:
                    node_parent.left_child=None
                else:
                    node_parent.right_child=None
            else:
                self.root=None

        # CASE 2 (node has a single child)
        if node_children==1:

            # get the single child node
            if node.left_child!=None:
                child=node.left_child
            else:
                child=node.right_child

            if node_parent!=None:
                # replace the node to be deleted with its child
                if node_parent.left_child==node:
                    node_parent.left_child=child
                else:
                    node_parent.right_child=child
            else:
                self.root=child

            # correct the parent pointer in node
            child.parent=node_parent

        # CASE 3 (node has two children)
        if node_children==2:

            # get the inorder successor of the deleted node
            successor=min_value_node(node.right_child)

            # copy the inorder successor's value to the node formerly
            # holding the value we wished to delete
            node.value=successor.value

            # delete the inorder successor now that it's value was
            # copied into the other node
            self.delete_node(successor)

            # exit function so we don't call the _inspect_deletion twice
            return

        if node_parent!=None:
            # fix the height of the parent of current node
            node_parent.height=1+max(self.get_height(node_parent.left_child),self.get_height(node_parent.right_child))

            # begin to traverse back up the tree checking if there are
            # any sections which now invalidate the AVL balance rules
            self._inspect_deletion(node_parent)

    def search(self,value):
        if self.root!=None:
            return self._search(value,self.root)
        else:
            return False

    def _search(self,value,cur_node):
        if value==cur_node.value:
            return True
        elif value<cur_node.value and cur_node.left_child!=None:
            return self._search(value,cur_node.left_child)
        elif value>cur_node.value and cur_node.right_child!=None:
            return self._search(value,cur_node.right_child)
        return False 


    # Functions added for AVL...

    def _inspect_insertion(self,cur_node,path=[]):
        if cur_node.parent==None: return
        path=[cur_node]+path

        left_height =self.get_height(cur_node.parent.left_child)
        right_height=self.get_height(cur_node.parent.right_child)

        if abs(left_height-right_height)>1:
            path=[cur_node.parent]+path
            self._rebalance_node(path[0],path[1],path[2])
            return

        new_height=1+cur_node.height 
        if new_height>cur_node.parent.height:
            cur_node.parent.height=new_height

        self._inspect_insertion(cur_node.parent,path)

    def _inspect_deletion(self,cur_node):
        if cur_node==None: return

        left_height =self.get_height(cur_node.left_child)
        right_height=self.get_height(cur_node.right_child)

        if abs(left_height-right_height)>1:
            y=self.taller_child(cur_node)
            x=self.taller_child(y)
            self._rebalance_node(cur_node,y,x)

        self._inspect_deletion(cur_node.parent)

    def _rebalance_node(self,z,y,x):
        if y==z.left_child and x==y.left_child:
            self._right_rotate(z)
        elif y==z.left_child and x==y.right_child:
            self._left_rotate(y)
            self._right_rotate(z)
        elif y==z.right_child and x==y.right_child:
            self._left_rotate(z)
        elif y==z.right_child and x==y.left_child:
            self._right_rotate(y)
            self._left_rotate(z)
        else:
            raise Exception('_rebalance_node: z,y,x node configuration not recognized!')

    def _right_rotate(self,z):
        sub_root=z.parent 
        y=z.left_child
        t3=y.right_child
        y.right_child=z
        z.parent=y
        z.left_child=t3
        if t3!=None: t3.parent=z
        y.parent=sub_root
        if y.parent==None:
                self.root=y
        else:
            if y.parent.left_child==z:
                y.parent.left_child=y
            else:
                y.parent.right_child=y        
        z.height=1+max(self.get_height(z.left_child),
            self.get_height(z.right_child))
        y.height=1+max(self.get_height(y.left_child),
            self.get_height(y.right_child))

    def _left_rotate(self,z):
        sub_root=z.parent 
        y=z.right_child
        t2=y.left_child
        y.left_child=z
        z.parent=y
        z.right_child=t2
        if t2!=None: t2.parent=z
        y.parent=sub_root
        if y.parent==None: 
            self.root=y
        else:
            if y.parent.left_child==z:
                y.parent.left_child=y
            else:
                y.parent.right_child=y
        z.height=1+max(self.get_height(z.left_child),
            self.get_height(z.right_child))
        y.height=1+max(self.get_height(y.left_child),
            self.get_height(y.right_child))

    def get_height(self,cur_node):
        if cur_node==None: return 0
        return cur_node.height

    def taller_child(self,cur_node):
        left=self.get_height(cur_node.left_child)
        right=self.get_height(cur_node.right_child)
        return cur_node.left_child if left>=right else cur_node.right_child

More info on binary search:

• Binary search basics
• Binary search trees explained with examples
• Binary data structures: intro to trees (and heaps)

1. Each tree has a root node (at the top) having some value.
2. The root node has zero or more child nodes.
3. Each child node has zero or more child nodes, and so on. This create a subtree in the tree. Every node has it’s own subtree made up of his children and their children, etc. This means that every node on its own can be a tree.

A binary search tree (BST) adds these two characteristics:

1. Each node has a maximum of up to two children.
2. For each node, the values of its left descendent nodes are less than that of the current node, which in turn is less than the right descendent nodes (if any).

The BST is built up on the idea of the binary search algorithm, which allows for fast lookup, insertion and removal of nodes. The way that they are set up means that, on average, each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree, O(log n).

However, some times the worst case can happen, when the tree isn’t balanced and the time complexity is O(n) for all three of these functions. That is why self-balancing trees (AVL, red-black, etc.) are a lot more effective than the basic BST.

Worst case scenario example: This can happen when you keep adding nodes that are always larger than the node before (it’s parent), the same can happen when you always add nodes with values lower than their parents.

Basic operations on a BST

• Create: creates an empty tree.
• Insert: insert a node in the tree.
• Search: Searches for a node in the tree.
• Delete: deletes a node from the tree.

Create

Initially an empty tree without any nodes is created. The variable/identifier which must point to the root node is initialized with a NULL value.

Search

You always start searching the tree at the root node and go down from there. You compare the data in each node with the one you are looking for. If the compared node doesn’t match then you either proceed to the right child or the left child, which depends on the outcome of the following comparison: If the node that you are searching for is lower than the one you were comparing it with, you proceed to to the left child, otherwise (if it’s larger) you go to the right child. Why? Because the BST is structured (as per its definition), that the right child is always larger than the parent and the left child is always lesser.

Insert

It is very similar to the search function. You again start at the root of the tree and go down recursively, searching for the right place to insert our new node, in the same way as explained in the search function. If a node with the same value is already in the tree, you can choose to either insert the duplicate or not. Some trees allow duplicates, some don’t. It depends on the certain implementation.

Delete

There are 3 cases that can happen when you are trying to delete a node. If it has,

1. No subtree (no children): This one is the easiest one. You can simply just delete the node, without any additional actions required.
2. One subtree (one child): You have to make sure that after the node is deleted, its child is then connected to the deleted node’s parent.
3. Two subtrees (two children): You have to find and replace the node you want to delete with its successor (the letfmost node in the right subtree).

The time complexity for creating a tree is O(1). The time complexity for searching, inserting or deleting a node depends on the height of the tree h, so the worst case is O(h).

Predecessor of a node

Predecessors can be described as the node that would come right before the node you are currently at. To find the predecessor of the current node, look at the right-most/largest leaf node in the left subtree.

Successor of a node

Successors can be described as the node that would come right after the node you are currently at. To find the successor of the current node, look at the left-most/smallest leaf node in the right subtree.

Special types of BT

• Heap
• Red-black tree
• B-tree
• Splay tree
• N-ary tree
• Trie (Radix tree)

Runtime

Data structure: Array

• Worst-case performance: O(log n)
• Best-case performance: O(1)
• Average performance: O(log n)
• Worst-case space complexity: O(1)

Where n is the number of nodes in the BST.

Implementation of BST

Here’s a definiton for a BST node having some data, referencing to its left and right child nodes.

struct node {
   int data;
   struct node *leftChild;
   struct node *rightChild;
};

Search Operation

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data){

      if(current != NULL) {
         printf("%d ",current->data);

         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }//else go to right tree
         else {                
            current = current->rightChild;
         }

         //not found
         if(current == NULL){
            return NULL;
         }
      }            
   }
   return current;
}

Insert Operation

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left

            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;

            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.

• To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
• To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.

Let’s look at a couple of procedures operating on trees.

Since trees are recursively defined, it’s very common to write routines that operate on trees that are themselves recursive.

So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:

• For instance, if we have a nil tree, then its height is a 0.
• Otherwise, We’re 1 plus the maximum of the left child tree and the right child tree.

So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.

Height(tree) algorithm

if tree = nil:
return 0
return 1 + Max(Height(tree.left),Height(tree.right))

Here is the code in C++

int maxDepth(struct node* node)
{
    if (node==NULL)
        return 0;
   else
   {
       int rDepth = maxDepth(node->right);
       int lDepth = maxDepth(node->left);

       if (lDepth > rDepth)
       {
           return(lDepth+1);
       }
       else
       {
            return(rDepth+1);
       }
   }
}

We could also look at calculating the size of a tree that is the number of nodes.

• Again, if we have a nil tree, we have zero nodes.

Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.

Size(tree) algorithm

if tree = nil
return 0
return 1 + Size(tree.left) + Size(tree.right)

Here is the code in C++

int treeSize(struct node* node)
{
    if (node==NULL)
        return 0;
    else
        return 1+(treeSize(node->left) + treeSize(node->right));
}

Relevant videos on freeCodeCamp YouTube channel

• Binary Search Tree
• Binary Search Tree: Traversal and Height

Following are common types of Binary Trees:

Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40

In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
 /  \   /
8   7  9

Red-Black Tree is a type of self-balancing Binary Search Tree (BST). In a Red-Black Tree, every node follows these rules:

1. Every node has two children, colored either red or black.
2. Every tree leaf node is always black.
3. Every red node has both of its children colored black.
4. There are no two adjacent red nodes (A red node cannot have a red parent or red child).
5. Every path from root to a tree leaf node has the same number of black nodes (called "black height").

Inserting into Red-Black Trees

A node is initially inserted into a Red-Black Tree just like any Binary Search Tree. The new node is then given a color of red. After that node has been inserted, the tree must be validated to ensure none of the five properties have been violated. If a property has been violated, there are three potential cases requiring either a left-rotation, right-rotation, and/or a recoloring of the nodes. The cases are dependent on the "uncle" of the current node. Specifically, whether the "uncle" node is black or red. For more info on inserting, the three cases can be found here.

Left-Leaning Red–Black Tree

A left-leaning red–black (LLRB) tree is a type of self-balancing binary search tree. It is a variant of the red–black tree and guarantees the same asymptotic complexity for operations, but is designed to be easier to implement.

Properties of Left Leaning Red-Black Trees

All of the red-black tree algorithms that have been proposed are characterized by a worst-case search time bounded by a small constant multiple of log N in a tree of N keys, and the behavior observed in practice is typically that same multiple faster than the worst-case bound, close to the optimal log N nodes examined that would be observed in a perfectly balanced tree.

Specifically, in a left-leaning red-black 2-3 tree built from N random keys: ->A random successful search examines log2 N − 0.5 nodes. ->The average tree height is about 2 log2 N

An AVL tree is a type of binary search tree. Named after it's inventors Adelson, Velskii, and Landis, AVL trees have the property of dynamic self-balancing in addition to all the other properties exhibited by binary search trees.

A BST is a data structure composed of nodes. It has the following guarantees:

1. Each tree has a root node (at the top)
2. The root node has zero, one, or two child nodes
3. Each child node has zero, one, or two child nodes
4. Each node has up to two children
5. For each node, its left descendants are less than the current node, which is less than the right descendants

AVL trees have an additional guarantee:

1. The difference between the depth of right and left sub-trees cannot be more than one. This difference is called the balance factor.

In order to maintain this guarantee, an implementation of an AVL will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee

AVL trees have a worst case lookup, insert, and delete time of O(log n), where n is the number of nodes in the tree. The worst case space complexity is O(n).

AVL Insertion Process

Insertion in an AVL tree is similar to insertion in a binary search tree. But after inserting and element, you need to fix the AVL properties using left or right rotations:

• If there is an imbalance in the left child's right sub-tree, perform a left-right rotation
• If there is an imbalance in the left child's left sub-tree, perform a right rotation
• If there is an imbalance in the right child's right sub-tree, perform a left rotation
• If there is an imbalance in the right child's left sub-tree, perform a right-left rotation

AVL Tree Rotations

In AVL trees, after each operation like insertion and deletion, the balance factor of every node needs to be checked. If every node satisfies the balance factor condition, then the operation can be concluded. Otherwise, the tree needs to be rebalanced using rotation operations.

There are four rotations and they are classified into two types:

Left Rotation (LL Rotation)

In left rotations, every node moves one position to left from the current position.

Right Rotation (RR Rotation)

In right rotations, every node moves one position to right from the current position.

Left-Right Rotation (LR Rotation)

Left-right rotations are a combination of a single left rotation followed by a single right rotation.

First, every node moves one position to the left, then one position to the right from the current position.

Right-Left Rotation (RL Rotation)

Right-left rotations are a combination of a single right rotation followed by a single left rotation.

First, every node moves one position to the right then, then one position to the left from the current position.

Application of AVL Trees

AVL trees are beneficial in cases like a database where insertions and deletions are not that frequent, but you frequently check for entries.

A tree is a data structure composed of nodes that has the following characteristics:

1. Each tree has a root node at the top (also known as Parent Node) containing some value (can be any datatype).
2. The root node has zero or more child nodes.
3. Each child node has zero or more child nodes, and so on. This creates a subtree in the tree. Every node has its own subtree made up of its children and their children, etc. This means that every node on its own can be a tree.

A binary search tree (BST) adds these two characteristics:

1. Each node has a maximum of up to two children.
2. For each node, the values of its left descendent nodes are less than that of the current node, which in turn is less than the right descendent nodes (if any).

The BST is built on the idea of the binary search algorithm, which allows for fast lookup, insertion and removal of nodes. The way that they are set up means that, on average, each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree, O(log n) . However, some times the worst case can happen, when the tree isn't balanced and the time complexity is O(n) for all three of these functions. That is why self-balancing trees (AVL, red-black, etc.) are a lot more effective than the basic BST.

Worst case scenario example: This can happen when you keep adding nodes that are always larger than the node before (its parent), the same can happen when you always add nodes with values lower than their parents.

Basic operations on a BST

• Create: creates an empty tree.
• Insert: insert a node in the tree.
• Search: Searches for a node in the tree.
• Delete: deletes a node from the tree.
• Inorder: in-order traversal of the tree.
• Preorder: pre-order traversal of the tree.
• Postorder: post-order traversal of the tree.

Create

Initially an empty tree without any nodes is created. The variable/identifier which must point to the root node is initialized with a NULL value.

Search

You always start searching the tree at the root node and go down from there. You compare the data in each node with the one you are looking for. If the compared node doesn't match then you either proceed to the right child or the left child, which depends on the outcome of the following comparison: If the node that you are searching for is lower than the one you were comparing it with, you proceed to the left child, otherwise (if it's larger) you go to the right child. Why? Because the BST is structured (as per its definition), that the right child is always larger than the parent and the left child is always lesser.

Breadth-first search (BFS)

Breadth first search is an algorithm used to traverse a BST. It begins at the root node and travels in a lateral manner (side to side), searching for the desired node. This type of search can be described as O(n) given that each node is visited once and the size of the tree directly correlates to the length of the search.

Depth-first search (DFS)

With a Depth-first search approach, we start with the root node and travel down a single branch. If the desired node is found along that branch, great, but if not, continue upwards and search unvisited nodes. This type of search also has a big O notation of O(n).

Insert

It is very similar to the search function. You again start at the root of the tree and go down recursively, searching for the right place to insert our new node, in the same way as explained in the search function. If a node with the same value is already in the tree, you can choose to either insert the duplicate or not. Some trees allow duplicates, some don't. It depends on the certain implementation.

Deletion

There are 3 cases that can happen when you are trying to delete a node. If it has,

1. No subtree (no children): This one is the easiest one. You can simply just delete the node, without any additional actions required.
2. One subtree (one child): You have to make sure that after the node is deleted, its child is then connected to the deleted node's parent.
3. Two subtrees (two children): You have to find and replace the node you want to delete with its inorder successor (the leftmost node in the right subtree).

The time complexity for creating a tree is O(1) . The time complexity for searching, inserting or deleting a node depends on the height of the tree h , so the worst case is O(h) in case of skewed trees.

Predecessor of a node

Predecessors can be described as the node that would come right before the node you are currently at. To find the predecessor of the current node, look at the right-most/largest leaf node in the left subtree.

Successor of a node

Successors can be described as the node that would come right after the the current node. To find the successor of the current node, look at the left-most/smallest leaf node in the right subtree.

Special types of BT

• Heap
• Red-black tree
• B-tree
• Splay tree
• N-ary tree
• Trie (Radix tree)

Runtime

Data structure: BST

• Worst-case performance: O(n)
• Best-case performance: O(1)
• Average performance: O(log n)
• Worst-case space complexity: O(1)

Where n is the number of nodes in the BST. Worst case is O(n) since BST can be unbalanced.

Implementation of BST

Here's a definition for a BST node having some data, referencing to its left and right child nodes.

struct node {
   int data;
   struct node *leftChild;
   struct node *rightChild;
};

Search Operation

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data){

      if(current != NULL) {
         printf("%d ",current->data);

         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }//else go to right tree
         else {                
            current = current->rightChild;
         }

         //not found
         if(current == NULL){
            return NULL;
         }
      }            
   }
   return current;
}

Insert Operation

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left

            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else {
            current = current->rightChild;

            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Delete Operation

void deleteNode(struct node* root, int data){

    if (root == NULL) root=tempnode; 

    if (data < root->key) 
        root->left = deleteNode(root->left, key); 


    else if (key > root->key) 
        root->right = deleteNode(root->right, key); 

    else
    { 
        if (root->left == NULL) 
        { 
            struct node *temp = root->right; 
            free(root); 
            return temp; 
        } 
        else if (root->right == NULL) 
        { 
            struct node *temp = root->left; 
            free(root); 
            return temp; 
        } 

        struct node* temp = minValueNode(root->right); 

        root->key = temp->key; 

        root->right = deleteNode(root->right, temp->key); 
    } 
    return root; 

}

Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.

• To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
• To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.

Let's look at a couple of procedures operating on trees.

Since trees are recursively defined, it's very common to write routines that operate on trees that are themselves recursive.

So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:

• For instance, if we have a nil tree, then its height is a 0.
• Otherwise, We're 1 plus the maximum of the left child tree and the right child tree.
• So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.

Height(tree) algorithm

if tree = nil:
    return 0
return 1 + Max(Height(tree.left),Height(tree.right))

Here is the code in C++

int maxDepth(struct node* node)
{
    if (node==NULL)
        return 0;
   else
   {
       int rDepth = maxDepth(node->right);
       int lDepth = maxDepth(node->left);

       if (lDepth > rDepth)
       {
           return(lDepth+1);
       }
       else
       {
            return(rDepth+1);
       }
   }
}

We could also look at calculating the size of a tree that is the number of nodes.

• Again, if we have a nil tree, we have zero nodes.
• Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.

Size(tree) algorithm

if tree = nil
    return 0
return 1 + Size(tree.left) + Size(tree.right)

Here is the code in C++

int treeSize(struct node* node)
{
    if (node==NULL)
        return 0;
    else
        return 1+(treeSize(node->left) + treeSize(node->right));
}

Traversal

There are 3 kinds of traversals that are done typically over a binary search tree. All these traversals have a somewhat common way of going over the nodes of the tree.

In-order

This traversal first goes over the left subtree of the root node, then accesses the current node, followed by the right subtree of the current node. The code represents the base case too, which says that an empty tree is also a binary search tree.

void inOrder(struct node* root) {
        // Base case
        if (root == null) {
                return;
        }
        // Travel the left sub-tree first.
        inOrder(root.left);
        // Print the current node value
        printf("%d ", root.data);
        // Travel the right sub-tree next.
        inOrder(root.right);
}

Pre-order

This traversal first accesses the current node value, then traverses the left and right sub-trees respectively.

void preOrder(struct node* root) {
        if (root == null) {
                return;
        }
        // Print the current node value
        printf("%d ", root.data);
        // Travel the left sub-tree first.
        preOrder(root.left);
        // Travel the right sub-tree next.
        preOrder(root.right);
}

Post-order

This traversal puts the root value at last, and goes over the left and right sub-trees first. The relative order of the left and right sub-trees remain the same. Only the position of the root changes in all the above mentioned traversals.

void postOrder(struct node* root) {
        if (root == null) {
                return;
        }
        // Travel the left sub-tree first.
        postOrder(root.left);
        // Travel the right sub-tree next.
        postOrder(root.right);
        // Print the current node value
        printf("%d ", root.data);
}

Relevant videos on freeCodeCamp YouTube channel

And Binary Search Tree: Traversal and Height

Following are common types of Binary Trees:

Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.

          18
         /   \
       /       \  
     15         30  
    /  \       /  \
  40    50   100   40

In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

           18
         /    \
       /        \  
     15         30  
    /  \       /  \
  40    50   100   40
 /  \   /
8    7 9

Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

          18
         /  \
       /      \  
     15        30  
    /  \      /  \
  40    50  100   40

Augmenting a BST

Sometimes we need to store some additional information with the traditional data structures to make our tasks easier. For example, consider a scenario where you are supposed to find the ith smallest number in a set. You can use brute force here but we can reduce the complexity of the problem to O(lg n) by augmenting a red-black or any self-balancing tree (where n is the number of elements in the set). We can also compute rank of any element in O(lg n) time. Let us consider a case where we are augmenting a red-black tree to store the additional information needed. Besides the usual attributes, we can store number of internal nodes in the subtree rooted at x(size of the subtree rooted at x including the node itself). Let x be any arbitrary node of a tree.

x.size = x.left.size + x.right.size + 1

While augmenting the tree, we should keep in mind, that we should be able to maintain the augmented information as well as do other operations like insertion, deletion, updating in O(lg n) time.

Since, we know that the value of x.left.size will give us the number of nodes which proceed x in the order traversal of the tree. Thus, x.left.size + 1 is the rank of x within the subtree rooted at x.

Awesome. That’s how I feel right now. Writing my first solo tech article.

I must say I have a lot to share with you guys, and have a lot more to learn as well. So without any further ado, lets get to it. And yes, hold on tight — ‘cause there is a twist in the tale. ?

Binary Search

All of us have heard of the classic 2 Eggs and 100 Stories problem. I have something similar for you.

You have a 100 story building with a rule:

**People with pets can only occupy top floors**

Your friend wishes to buy an apartment in this building. She is too scared of pets to live near them, but you love them. She asked if you can help her find out where exactly the pet friendly floors start. She wants to explore all of the different options available, and so you need to find out which floors starting from the ground up are the ones that don’t allow pets.

The building management folks are on a holiday. On every floor, there is a sign board next to the elevator telling you if the floor is pet friendly or not. But you are too lazy to stop at every floor to check the pet sign board since the lift is so slow.

What do you do?

The two possible sign boards. #GoRed is what your friend roots for.

The lift takes almost a minute at every floor to stop and then start again. Yes that’s how bad it is. But between the floors, navigation is pretty smooth. You have to get this done quickly.

How do you go about it ?

Iterative approach

One naïve approach to this would be to start at the very bottom of the building (the ground floor) and keep stopping the lift at every single floor to check the sign that floor has posted. You stop when you find the pet friendly sign.

Best case is that the ground floor has the pet sign. Meaning the entire building has pets. No way your friend would buy an apartment here.

Average case is that you go to the 50th floor, stopping at every floor in between, and finally find a pet sign board. So your friend can buy one from 1–49.

Worst case scenario would be you reaching the 100th floor, stopping at every floor on the way up, only to find out that there are no pet sign boards in the entire building. So your friend can buy any apartment from 1–100, but who cares, it took you almost two hours to find that out. ? ?.

Algorithmically, given an array of 100 boolean values, the index of the array represents building floors and a 0 represents a floor where no pets are allowed while a 1 represents a floor where pets would be allowed. From the rule of the building, the array would be of the form

000... 1111...

that is, all 0s followed by all 1s, because only the top floors can be the ones where pets are allowed.

Given this array, we need to find the first index where there is a 1 . A linear search algorithm for this problem would be as simple as iterating over the array and looking for a 1 and returning when we find one.

As expected, the complexity of this algorithm would be O(n) where n = 100 for our specific building example. You need to come up with something faster than this. Stopping at every floor is not feasible, as it would take you a lot of time to cover the entire building in the worst case.

Binary Search Approach

Let’s say you start from ground floor and got to the 50th floor with no stops. At the 50th floor, you stopped and got out of the lift and checked for the sign. The board sign said “No Pets”. This would mean that, until the 50th floor, there are definitely no pets.

So now knowing that you reduce your search space to the other half, which is floors 51–100. This means that with a single stop, you were able to cover half of the building knowing for sure that the first half doesn’t have any pets. That’s amazing!

Moving on, you again divide your remaining set of floors into half and take the lift and go directly to the 75th floor. And you see a “Pets” sign board there. This means the floor where it started showing up must be between 50–75. You can keep following a similar approach of diving the remaining floors into half and checking until you find the first floor with the “Pets” sign board.

You see, every time you make a decision, you divide your search space into two halves and go ahead with one half of the search space. That’s how we narrow down our search. Since we always divide the search space in two and choose one over the other, that is why this type of search strategy is called a Binary search strategy.

Isn’t that way faster?

Let’s look into the algorithm for this.

Binary Search Algorithm

If you’ve been following along closely and have a grasp of the algorithm, you would have realized a hard and fast condition for the binary search algorithm to work. The condition is that the array needs to be sorted beforehand. In our example, the building floors were sorted from 1–100 and we could easily divide the search space in two.

Let’s look at an example array which is sorted and try and search for an element in it.

In the above example, the element to be searched is 8. The given array is a sorted array in increasing order. Once we find the middle element (which is 5), we see that the element to be searched is greater than the current index element. Since the array is sorted in increasing order, 8 would lie on the right of the array and can never be on the left side.

So we ignore the elements to the left of 5 and continue our search with the remaining elements, eventually finding out 8.

On the other hand, what if the array is not sorted? Even though we know the current element is 5 and we know we need to search for 8, we are not sure which direction is the right way to go. If we end up thinking the array is sorted and apply binary search and go to the right part, we will never find 8.

So binary search essentially wants your array to be sorted.

That was the standard binary search algorithm that we just looked at. But, as the title of the article suggests, there is a twist in the tale!

I am an avid competitive programmer, and there was an interesting variant of the binary search algorithm in the CodeChef May Long Challenge.

Essentially, the Chef wrote the classic binary search, assuming the input array would be sorted. All the other children in the class copied the code from him, as Chef is the best programmer in the class. His assumption could’ve cost the entire class their assignment marks, as the input array was not sorted beforehand.

The only thing the Chef can do is to preprocess the array by swapping some pair of numbers here and there so that the binary search procedure still returns the right index.

Note: The preprocessor above should ideally return the modified array for the binary search to work correctly. However, as the problem statement asks, we are just trying to determine the number of swaps needed for binary search to work correctly on the unsorted array given an input. The algorithm would also return a -1 if such a modification is not possible for the given array and element.

The idea here is very simple.

We need to understand two basic steps. I call them the TI-ME steps. Perhaps that’ll help you remember what we are doing here.

a. Target Index: The index of the element to be searched for. We need to know this, since this index would help us drive the modifications. Because every time we modify any element, we need to sail towards this index and not away from it.

b. Middle Element: If you look clearly in a binary search, it’s the middle element of the current search space which drives the next move. If this middle element takes us in the wrong direction, we need to replace with the appropriate element.

We are searching for 8 in the above unsorted array. We already saw in the examples above a normal binary search would fail for an unsorted array.

Mid elements give direction to binary search. Middle element 5 would take binary search to go right. This way we would never find 8. If we swap 5 with an element greater than 8 we would force the search to go to left.

So, the whole idea here is that we swap all the middle elements which are wrongly placed.

The binary search algorithm (the value of the middle element with respect to the element to be searched, that is, X) can either take us towards the left half of the array or the right half. So, there are two possibilities for a wrongly placed middle element:

1. The element to be searched was on the right of the middle element, but since Element[Mid] > Element[Target Index] , the binary search would have had to ignore the right half and move towards the left half. OR
2. The element to be searched was on the left of the middle element, but since Element[Mid] < Element[Target Index] , the binary search would have had to ignore the left half and move towards the right half.

Therefore, if a middle element is wrongly placed such that a number X was needed in its place where X < Element[Target Index] , then we maintain a counter for that and call it count_low_needed .

Similarly, if a middle element is wrongly placed such that a number X was needed in its place where X > Element[Target Index] , then we maintain a counter for that and call it count_high_needed .

Also, if we simply run the binary search algorithm over the given array while searching for numbers, there would be some numbers that would be correctly placed. These would be the middle elements that drove the binary search in correct directions corresponding to the given element X (the element to be searched). These numbers cannot be a part of the swapping, because they are rightly positioned with respect to X .

Let’s look at the pseudo code for this algorithm first and then go through an example.

function can_preprocess(arr, X){     low = 0     high= 0

while X is not found {          mid = (low + high) / 2          if arr[mid] == X {             break                     }

correctly_placed_low = 0          correctly_placed_high = 0          count_low_needed = 0          count_high_needed = 0

if `mid` suggests we should go right for X {               if X is actually on the right {                   correctly_placed_low ++               }               else {                   count_low_needed ++               }          } else {               if X is actually on the left {                  correctly_placed_high ++               }                else {                  count_high_needed ++               }          }

modify low and high according to           where `X` actually is with respect to `mid`

}

// Total smaller numbers available for swapping     TSM = sorted_index[X] - correctly_placed_low

// Total Larger numbers available for swapping     TLM = (N - sorted_index[X]) - correctly_placed_high

if count_low_needed > TSM or count_high_needed > TLM {          return -1     }

return max(count_low_needed, count_high_needed)

NOTE: The problem statement fixes the input array for us and repeatedly passes values to be searched in the input array. So, we can iterate once over the original array to know the actual location of the element to be searched (create a dictionary, essentially).

Also, we need sorted_index[X] to tell us how many values are lesser than or greater than the element X in our array. We can sort the array and create another dictionary storing location of each element in the sorted array.

Let’s go through the steps of the proposed algorithm while dry running an example.

1. Given an unsorted array, you need to search for X = 4 .
   Hence our target index is 7.

2. Mid element index < Target Index, so we need to maneuver our search to the right half. But Element[Mid] > Element[Target Index], hence count_low_needed = 1

3. Mid element index < Target Index, so we still need to maneuver our search to the right half. Once again, Element[Mid] > Element[Target Index], hence count_low_needed = 2

4. The total number of swaps needed for binary search to return the correct index here would be two swaps with elements lower than 4. We have smaller numbers 1, 3 or 2 for swapping available, so we can successfully do the swapping for this array so that binary search correctly finds out 4 .

Below is the Python code for the given problem. Every step is explained in the comments.

The time complexity of this Twisted Binary Search algorithm is still O(nlogn) .

I hope you were able to grasp the inner workings of the binary search algorithm and had fun while going through this interesting problem as well. If you found this post useful, spread the love and share as much as possible. ?