Binary Tree

First thing is first, we need to understand what a Binary Tree is. There are other various of trees such as Binary Search Tree and AVL Tree which is named after the inventor Adelson-Velskii and Landis but we will look into that at a later date.

However, in this post, we are going to look at Binary Tree and understand how this data structure works and how we can use it by implementing in Java. We will also look at the worst-case time complexity for operations such as access/search/insertion/deletion.  Towards the end, we will create an example and I will provide you with sample code on how this can be implemented.

What is a Binary Tree?

So first things first, what is a Binary Tree? As you might think a tree is a hierarchical structure consisting of nodes. As you might think its the same a normal tree in real life. See figure1  an example of a Binary Tree.

A basic Binary Tree
Figure1

Tree Terminology

Have a look at figure2 below to get an understanding of each part of the tree and what they represent.

 

 

 

 

 

 

 

 

Trees are acyclic. This means there are no cycles, i.e. there are no nodes pointing backwards in the tree. The height of a tree is the length of the longest path from the root to the leaf node. So the height in the above example is 4. The depth of a given node is the length of the path from the root to that node, e.g. the depth of B is 2.

A Binary Tree can only be a true Binary Tree where each node has either 0, 1 or 2 children.

Traversing A Binary Tree

There are 2 algorithms of traversing a Binary Tree. We will have a brief overview at each of them and we will also be implementing them in our implementation at the end of the post.

Breadth-First Search

A basic Binary Tree

A breadth-first search visits the nodes in the order of each level. If we use the same tree from figure1 as an example. The breadth-first search for that tree is 2,7,5,2,6,9,5,11,4

Depth-First Search

A depth-first search travels recursively (if you do not know what this is keep posted for future posts) down to the leaves and then back up.

A depth-first search can be either:

Pre-Order: Visit the root and then the sub-trees, e.g. Using the tree above the results for a pre-order search is 2,7,2,6,5,11,5,9,4
Post-Order: Visit the sub-trees and then the root. e.g. Using the tree above the results for a post-order search is 2,5,11,6,7,4,9,5,2
In-Order: This is usually for Binary Trees where there are two sub-trees. Visit the left sub-tree, then the root and then the sub-right tree. 2,7,5,6,11,2,5,4,9

Worst-Case Time Complexity

We will take a look at the time worst-case time complexity or otherwise known as Big-O notation.

Access – O(log n)
Search – O(log n)
Insertion – O(log n)
Deletion – O(log n)

Implementing A Binary Tree

package lib;

public class Node {
    private Node left, right;
    private int data;

    public Node(int data) {
        this.data = data;
    }

    public void insert(int value) {
        if(value <= data) {
            if(left != null) {
                left = new Node(value);
            } else {
                left.insert(value);
            }
        } else {
            if(right != null) {
                right = new Node(value);
            } else {
                right.insert(value);
            }
        }
    }

    public boolean contains(int value) {
        if(value == data) {
            return true;
        } else if (value < data) {
            if(left == null) {
                return false;
            } else {
                return left.contains(value);
            }
        } else {
            if(right == null) {
                return false;
            } else {
                return right. contains(value);
            }
        }
    }


    public void printInOrder() {
        if(left != null) {
            left.printInOrder();
        }
        System.out.println(data);
        if(right != null) {
            right.printInOrder();
        }
    }

    public void printPreOrder() {
        System.out.println(data);
        if(left != null) {
            left.printInOrder();
        }
        if(right != null) {
            right.printInOrder();
        }
    }

    public void printPostOrder() {
        if(left != null) {
            left.printInOrder();
        }
        if(right != null) {
            right.printInOrder();
        }
        System.out.println(data);
    }

}

 

How to use the list() Data Structure

In Python and in most programming languages such as Java lists are mutable, which means lists are able to change. To create a list in Python is very straightforward and we can do this by doing the following:

# List created having int's, strings and float's 
my_list = [1,2,3,"Daniel", "Maia", 2.3]

You will notice you can create a list containing different data types such as int, string, and floats. As you can see its very straightforward to do, you will find in other programming languages it’s similar syntax. You will notice the list is also assigned to the variable my_list  with this you can reference the variable name across your project and access contents in that list.

If you like to play with lists, you can also create a list like, [“daniel”, “maia”, 1,2,3]  and run this in your terminal and it will display the list to you, however, you cannot reference that list unless you assign a variable to it as we did above. Like so:

Moving on…. we can create a list within a list. What do I mean by this? Well, if we take the list of our first example we can create a list of this list. This is how you would do that:

my_list_2 = [1, 2, 3, 'Daniel', 'Maia', ["Another", "List"]]

Now you might be thinking, ok well…. how do I access that second list? This brings me to my next section on accessing elements in a list. To be able to access an element in your list, all you need to do is to call you variable followed by [] so here is an example on how to access the first element in the list:

# Created list, as in our first example
my_list = [1,2,3,"Daniel", "Maia", 2.3]

# Accessing the first element in the list
my_variable[0]

In any programming language, you will find  is the first element or seen as the computers number 1. Computers start counting at number 0 not like us, human, where we start at number 0. Anyway, so the result of this you will get the first element being 1. This is the same as accessing the second list, you just need to reference the index of the second list which in this case it’s 5, however, note that when you access the second list you are accessing all the elements in that second list. Here is an example:

# Basic List
my_list_2 = [1, 2, 3, 'Daniel', 'Maia', ["Another", "List"]]

# Access the first element in the list
my_list[0]
>> 1

# Accessing the second list ["Another", "List"]
my_list[5]
>> ["Another", "List"]

# To access the second list and the first element in that list
my_list[5][0]
>> ["Another"]

Try this on your terminal if you have Python installed on your machine, if not follow the guide relevant to your operating system on one of my other blog posts.

Continuing on with lists, let’s move on to how we can add items to the list:

# Gowing lists:
favourite_things = ["raindrops on roses", "whiskers on kittens", "bright copper kettles"]

# Can a new item to the list by using the + operand as below: NOTE: This is not permanent
favourite_things + ["warm wollen mittens"]

# To make it permanent you will need to use the +=
favourite_things += ["warm wollen mittens"]

There are built-in functions within Python which will allow you do things like this. Those functions are:

  • append()
  • extend()
  • insert()
  • pop()
  • remove()

I will explain each of these in more detail:


append()

Let’s start with append(), append will append whatever value you specify to the end of the list. Here is an example:

# A simple 1 dimensional list
my_list = [1,2,3,"Daniel", "Maia", 2.3]

# To add an item with the append() method, as just an item and not another list:
my_list.append("Another item 1")

As you can see all you need to do is specify which list you want to add the elements to, so in this case my_list then followed by append(“Another item 1”) the string between the () is the element which will be added to the list. If you run this code you’re the item “Another item 1” is now added to the end of my_list list. You will see an output like so:

# The new list will be: 
[1, 2, 3, 'Daniel', 'Maia', 2.3, 'Another item 1']

extend ()

The extend function is slightly different, if you use the extend function as long as the argument is iterable then every element in the argument is then added to the list as its own element in the list, here is an example:

# Another option is the extend() function, this takes a list [] and adds it to another list as items
favourite_things.extend(["item added 2", "items added 3"])

# When you run it 'item added 2', 'items added 3' has been added to the list
# This can be done as long as the item is iterable so:
a = [1,2,3]
a.extend("abc")
# This will return [1, 2, 3, 'a', 'b', 'c']

insert()

This function allows you to enter an element at a specific index, so this example “Added to the begining og the list” is added to the beginning as the 0 index is specified

# The insert() function takes 2 arguments the index, where in the list you want the item to go and then the item itself
my_list.insert(0, "Added to the begining of the list")

pop()

Removes the item from the list but returning the value back to  you, see the examples of pop() below

# 1. Create a list
my_list = [1,2,3,4,5]

# Remove an item and return it using the index
my_list.pop(0)

# Now we can use pop() and assign it to a variable like so:
element = my_list.pop(0)
# Now we can access the element variable whenever we want but you will notice the my_list list no longer has that variable

remove()

As you can tell by the name, the remove() function removes elements in the list, however when using this function if there is more than one element that’s the same and use remove it will only remove the first instance.

remove_list = [1,2,3,1]
remove_list.remove(1)
remove_list.remove(1)
# Now it will remove all the 1's in the list

 

I hope you got to grips with how lists work in Python from this post, if not, or have questions about it please let me know and I will be happy to help. You can view all my source code here on Github

Variables, Strings & Arithmetic

Variables

The first part of Python we are going to talk about is variables. What are they and what are they used for, in simple terms a variable is a box where you can store any information you like and then return to that box to retrieve the item.

In this example the name of the variable is name and the name Maria in stored in that box to then retrieve later. In Python, we do that by doing the following:

name = "Maria"

As you can see its easy enough to do. A string is surrounded by double quotes ” ” and numbers or known as integers are just created without doubles quotes. See example below:

current_count = 14
planned = 5

Once the variable has been created, you can then delete the variable by using the keyword del  this will look for the variable in memory and remove it. If you run the following code you will see at the end you wont be able to access the variable:

# Variable my_variable is created with the value "Daniel"
my_variable = "Daniel"

# The print command is used to print the values to the screen
# At this point the print(my_variable) will print Daniel
print(my_variable)

# Will delete the variable
del my_variable

# Then if you run the print() command again the variable no longer exists and you will get the follwoing error
print(my_variable)

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'my_variable' is not defined

Arithmetic

In Python 3 there are 3 data types, these include:

  • Int – This is whole numbers such as 1 2 3 or 45
  • Float – Numbers with a decimal point, such as 3.4 4.5 14.5 ect…
  • Complex – (Back back to this)

The first slight difference you will find in Python 2 compared to Python 3 is that the results for the basic operation of division. When you divide whole numbers on Python 2 it will return an int. However, in Python 3 it will always return a float. Here is an example:

# Python 3 Divison Output
>> 8/2
>> 4.0
# Python 2 Division Output 
>> 8/2 
>> 4

If you were to divide by 0 on Python 3 you will receive a “ZeroDivisionError: integer division or modulo by zero” so dividing by 0 is not possible in Python 3. Going back to using basic data types in Python, there is a function round() this is a very useful function which will round a float to the nearest whole number. Here is an example of how this works:

# Python round() function
round_me = 5.4
round(round_me)
>> 5.0

There is a function which is also useful and that’s the int()  this will return an int value, here is an example of how the int() function works:

# int() - returns an int from a float
>> int(5.4)
>> 5

Then we have a float() function, this allows us to do the opposite of int(). With the float() function it allows us to convert an int such as 1 or 2 to be converted to 1.0 or 2.0. Here is an example of how this works:

# float() - Converts int's to floats
>> float(4)
>> 4.0

Along with all these functions Python, of course, understands basic arithmetic operations such as adding 2 numbers together, multiplying, subtraction or division as you have seen previously. Here are some examples of addition, multiplying and division.

# Addition
>> 5+4
>> 9
# Mutlpying 
>> 5*4 
>> 20
# Division 
>> 5/4 
>> 1

You will find the common and basic arithmetic operators are as follows:

  • 4+5  addition
  • 54  Subtraction
  • 5/4 Division
  • 5*4 Multiplication

As you probably have learnt at school the famous BODMAS, which relates to the order of precedence in arithmetic operations in algebra etc… well Python understands the order of precedence but you have to explicitly have to change the order and you can do this by using the parentheses () Here is an example of how you can do this:

# Without order of precedence
>> 5*6+5
>> 35
# With Order of Precedence 
>> 5*(6+5) 
>> 31

As you can see the results differ and this is because I explicitly changed the order I want the calculations to be performed

Strings

Strings is a group of characters between double or single quotes, like so:

# String example assigned to a variable
world_message = "Hello World"

However, the one thing that needs to be taken into consideration is when creating strings, is the when it comes to having single quotes for names for the word such as He’s right 

# This will generate an error, 
variable = "He's right"

# The way to avoid this by placing a backslash before the single quote
variable = "He\'s right"

# Another way to ignore the single quote
variable = """He's right"""

As we have seen earlier, we can also the + operator to add 2 or more numbers together, however, we can also use the + to join strings together this is called concatenation, as an example:

# Join string together with +
>> "test" + "123"
>> test123

You will also notice that there is no space between test and 123 this is because you need to leave a space either at the end of the first string or at the begining of the second string, like so:

# Concatenating
>> "test " + "123"
>> test 123
# Or 
>> "test" + " 123" 
>> test 123

You can do this with the basic operators:

# Multiplying a string
>> "="*20
>> ====================

However, say you want to add multiple variables in a string based on what the user input? You will want to enter that into the string for example, The user enters their first and last name in your program and you want to output a message to the user saying something like “Welcome Daniel your last name is Maia and this is not a common name” You can do this using the format() function. You use this function as such as:

# format() function
fname = "Daniel"
lname = "Maia"
print("Welcome {} your last name is {} and this is not a common name".format(fname, lname))

>> Welcome Daniel your last name is Maia and this is not a common name

You will notice that I used a function called print()  this will allow you to print to the screen.

If there is anything you did not understand, drop a comment below or drop me an email and I will be happy to answer your questions 🙂

Installing Python 3 on Windows

Python: Version 3.6.5

The Python download requires about 30 Mb of disk space; keep it on your machine, in case you need to re-install Python. When installed, Python requires about an additional 90 Mb of disk space.

Installing on Windows

1.Click here to be redirected to the Python Download page.

A page similar to the below will appear:

2. Click the Download Python 3.6.5 button.

The file named python-3.6.5.exe should start downloading into your standard download folder. This file is about 30 Mb so it might take a while to download fully if you are on a slow internet connection (it took me about 10 seconds over a cable modem).

The file should appear as

3. Move this file to a more permanent location, so that you can install Python (and reinstall it easily later, if necessary).

4. Feel free to explore this webpage further; if you want to just continue the installation, you can terminate the tab browsing this webpage.

5. Start the Installing instructions directly below.


Installing

1. Double-click the icon labeling the file python-3.6.2.exe.

An Open File – Security Warning pop-up window will appear.

2. Click Run.

Python 3.6.5 (32-bit) Setup pop-up window will appear.

Ensure that the Install launcher for all users (recommended) and the Add Python 3.6 to PATH check boxes at the bottom is checked.

If the Python Installer finds an earlier version of Python installed on your computer, the Install Now message will instead appear as Upgrade Now (and the checkboxes will not appear).

3. Highlight the Install Now (or Upgrade Now) message, and then click it.

User Account Control pop-up window will appear, posing the question Do you want the allow the following program to make changes to this computer?

4. Click the Yes button.

A new Python 3.6.5 (32-bit) Setup pop-up window will appear with a Setup Progress message and a progress bar.

During installation, it will show the various components it is installing and move the progress bar towards completion. Soon, a new Python 3.6.5 (32-bit) Setup pop-up window will appear with a Setup was successfully message.

5. Click the Close button. Python should now be installed.


Verifying

To try to verify installation,

  1. Navigate to the directory C:\Users\Pattis\AppData\Local\Programs\Python\Python36-32 (or to whatever directory Python was installed: see the pop-up window for Installing step 3).
  2. Double-click the icon/file python.exe.The following pop-up window will appear.

A pop-up window with the title C:\Users\Pattis\AppData\Local\Programs\Python\Python36-32 appears, and inside the window; on the first line is the text Python 3.6.5 … (notice that it should also say 32 bit). Inside the window, at the bottom left, is the prompt >>>: type exit() to this prompt and press enter to terminate Python.

You should keep the file python-3.6.5.exe somewhere on your computer in case you need to reinstall Python (not likely necessary).

You may now follow the instructions to download and install Java (if you have not already done so), and then the instruction to download and install the Eclipse IDE (for Python, Java, or both ). Note: you need to download/install Java even if you are using Eclipse only for Python)

Installing Python 3 on Linux

We will take a look at how to install Python 3 on a Linux machine. This is not specific to a Linux Distribution as it should apply to all. If you get stuck or require some help please post a message on the comments below or drop me a a message directly.

Open a new terminal and follow the below commands:

$ sudo apt-get install python3
$ sudo apt-get update
  • On Red Hat and derivatives, use yum:
$ sudo yum install python
  • On SUSE and derivatives, use zypper:
$ sudo zypper install python3

To check if Python is now installed type the following:

$ python --version

You should now see something like this:

$ python -version
Python 3.6.2

 

 

Install Python 3 on Mac OSX

Before installing Python, you’ll need to install a C compiler. The fastest way is to install the Xcode Command Line Tools by running.xcode-select –install You can also download the full version of Xcode from the Mac App Store, or the minimal but unofficial OSX-GCC-Installer package.

Note: If you already have XCode installed, do not install OSX-GCC-Installer. In combination, the software can cause issues that are difficult to diagnose.

Note: If you perform a fresh install of XCode, you will also need to add the command line tools by running on xcode-select –install the terminal.

While OS X comes with a large number of UNIX utilities, those familiar with Linux systems will notice one key component missing: a decent package manager. Homebrew fills this void.

To install Homebrew, open terminal or your favorite OSX terminal emulator and run

$ /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

The script will explain what changes it will make and prompt you before the installation begins. Once you’ve installed Homebrew, insert the Homebrew directory at the top of your PATHenvironment variable. You can do this by adding the following line at the bottom of your ~/.profile file

export PATH="/usr/local/bin:/usr/local/sbin:$PATH"

Now, we can install Python 3:

$ brew install python@3

Because python@3 is a “keg”, we need to update our PATH again, to point at our new installation:

export PATH="/usr/local/opt/python@3/libexec/bin:$PATH"

Homebrew names the executable sopython3 that you can still run the system Python via the executable.python

$ python -V   # Homebrew installed Python 3 interpreter (if installed)
$ python2 -V  # Homebrew installed Python 2 interpreter
$ python3 -V  # Homebrew installed Python 3 interpreter (if installed)

Setuptools & Pip

Homebrew installs Setuptools and pip for you.

Setuptools enables you to download and install any compliant Python software over a network (usually the Internet) with a single command (easy_install). It also enables you to add this network installation capability to your own Python software with very little work.

pip is a tool for easily installing and managing Python packages, that is recommended over.easy_install It is superior to ineasy_install several ways, and is actively maintained.

$ pip2 -V  # pip pointing to the Homebrew installed Python 2 interpreter
$ pip -V  # pip pointing to the Homebrew installed Python 3 interpreter (if installed)