After CompSci

What is a Binary Tree

A binary tree is a data structure that consists of nodes in a tree. Each node has three attributes: a value and a left and right child node. As simple binary tree would look like the following:

     1
    / \
   3   2
  /     \
4        5

What is a Binary Search Tree

A binary search tree is a data structure that consists of nodes in a tree. Each node has three attributes: a value, and a left and right child node(these are null if it’s a leaf node). A simple binary search tree would look something like this.

     4
   /    \
  2      5
 /  \     \
1    3     6

The one defining characteristic of a BST vs a standard binary tree is that in a BST the left value of left node must be less than the value of the parent node value and the right node value must be greater than the parent node value.

Creating a Binary Search Tree

For our first dive into BSTs we need to be able to create one. The easiest way to do this would be to take in an array of node values and then create a BST from them.

In this example we can think of the execution as follows

• Get the array

• Sort the array

• in a function that we can call recursively pass in an array

• if the array is of size 0, return None

• get the middle index of the array

• set the node value as the arr[middle] array value

• set the node left child node to call the function with the arr[:mid] as input

• set the node right child node to call the function with the arr[mid+1:] as input

• return the node you created

The function should then look something like this:

def createBSTFromSortedList(arr: list) -> BinarySearchTreeNode:

if len(arr) == 0:

return None

mid = len(arr) // 2

root = BinarySearchTreeNode(arr[mid])

# set the left as the middle node - 1 index

root.left = createBSTFromSortedList(arr[:mid])

# set the right as the middle node + 1 index

root.right = createBSTFromSortedList(arr[mid+1:])

return root

> Make sure that you use the // division operator so that you receive an int and not a float for the index.

Question: Given an array build out a binary tree

Pick out your favorite sorting algorithm or utilize the built in sorting function for arrays if your language has it available. Luckily for us Python does have a built in sorting function for arrays which uses Tim Sort. Then pass that sorted array to the function we defined above to build out the binary search tree.

The time to build this tree is then O(n * log(n)) for the sort plus `O(n)` for the creation of the binary search tree. This results in a time complexity of O(n * log(n)) This is only the case if you know all of the element in advance though. When you know all of the elements in advance it is known as an `offline algorithm`. When you do not know all of the elements in advance and only receive the elements one at a time it is known as an `online algorithm`.

If the elements are not all known ahead of time it could take as long as O(n) for the insertion time of each element times the n elements which would result in a time complexity of O(n^2).

Balanced Binary Trees

There are balanced and unbalanced binary trees. Balanced binary trees have a a maximum height of O(log(n)). Two of the most popular data structures for self balancing BSTs are AVL Trees and Red Black Trees.

These balanced binary trees ensure that the insertion, search and deletion are all possible in O(log(n)) time.

Time Complexity Overview

Insert: O(log(n))

Search: O(log(n))

Delete: O(log(n))

Build Complexity Online: O(n log((n))), worst case O(n^2)

Build Complexity Offline: O(n log((n)))

Interesting link of the week

Cool but obscure data structures

Thanks for reading this week, in our next installment we will take a look at N-ary trees and some more BST questions. If there are any questions or data structures you’d like to add to the queue please send an email out to allen@aftercompsci.com .