Binary Search Tree implementation in Python

In this post, we’ll see how to implement a Binary Search Tree. A tree can be qualified as Binary Search Tree (BST) when it satisfies the following condition :

  1. Root node is not null
  2. All the left sub-tree and its children have a value less than or equal to value of root
  3. All the right sub-tree and its children have a value greater than the value of root

Let’s see the TreeNode implementation in python below :


The implementation of the Tree object is below. The Tree class has the method for all the 3 modes of tree traversal

a)Pre Order Traversal (parsing order root->left subtree —->right subtree )

b)In Order Traversal (parsing order left subtree –> root —> right subtree )

c)Post Order Traversal (parsing order left subtree –> right subtree –> root)

from Node import Node

class Tree:

    def __init__(self, rootdata):
        self.root = Node(rootdata)
    
    def AddNode(self,root,data):

        if data < root.data:
            print('to be inserted on left subtree')
            if root.left is None:
                root.left = Node(data)
                print('New node added on left'+str(data))
            else:
                self.AddNode(root.left,data)
            
        elif data > root.data:
            print('to be inserted on right subtree')
            if root.right is None:
                root.right = Node(data)
                print('New node added on right'+str(data))
            
            else:
                self.AddNode(root.right,data)


    def PreOrderTraversal(self,root):

        if root is not None:
            print(root.data)
            self.PreOrderTraversal(root.left)
            self.PreOrderTraversal(root.right)

    def InOrderTraversal(self,root):

        if root is not None:

            self.InOrderTraversal(root.left)
            print(root.data)
            self.InOrderTraversal(root.right)
            
    def PostOrderTraversal(self,root):

        if root is not None:
            self.PostOrderTraversal(root.left)
            self.PostOrderTraversal(root.right)
            print(root.data)


      

The driver code for running this Tree is below :

When you run this code, you should get the following output.

BnarySearchTree/BinaryTreeDriver.py
to be inserted on left subtree
New node added on left14
to be inserted on right subtree
New node added on right35
to be inserted on left subtree
to be inserted on left subtree
New node added on left10
to be inserted on left subtree
to be inserted on right subtree
New node added on right19
to be inserted on right subtree
to be inserted on left subtree
New node added on left31
to be inserted on right subtree
to be inserted on right subtree
New node added on right42
Output of preorder traversal
27
14
10
19
35
31
42

Output of inorder traversal
10
14
19
27
31
35
42
Output of postorder traversal
10
19
14
31
42
35

Selection Sort Algorithm using C#

Selection Sort Algorithm is one of the simplest sorting algorithm like BubbleSort. However this is not efficient when it comes to TimeCompexity.

Overview

In this algorithm we try to divide the array into two halves – sorted half and unsorted half. In the first pass, the sorted half contains the first element of the array. In the first pass, we compare the first element (from the sorted half) against the first element in the unsorted half. If first element (in sorted half) is greater than the first element in the unsorted half, we do a swapping of these two items. We continue this process until we finish comparing all elements in the unsorted half. At the end of the first pass, we make sure that first element in the array is the lowest one.This is one pass.

In the second pass, we consider 2nd element in the array and compare against each and every element in the unsorted half. We continue with passing for n-1 iterations (covering up to n-2 th item in the sorted half).

Advantages

  1. Easy to implement the algorithm
  2. In-place sort requires no additional memory for storage

Pseudocode

//Outer loop for passes

for (int i=0 ; i<num.Lenth-1 ; i++)

{

// Inner loop for check and pass

for (int j = i+1; i<num.length;i++)

{

//Check and Swap

if(num[i] > num[j])

{

//Do a swap

temp = a[[i];

a[i] = a[j];

a[j] = temp;

}

}

}

Implementation in C#

using System;

namespace SelectionSort
{
    class Program
    {
        static int [] num = {8,6,5,7,1,2,3};
        static int swapcount = 0;
        static int swapcheck = 0;
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            SelectionSort();
            PrintSortedItems();
        }

        static void SelectionSort()
        {
         
           //Outer loop for number of passes till n-2 th item in the array
            for (int i = 0; i < num.Length-1; i++)
            {
                   int minIndex = i;
                   int passcount = i+1;
                
                Console.WriteLine("This is pass number ----->"+passcount);

                //Inner loop for checking to perform a swap
                for (int j = i+1; j < num.Length; j++)
                {
                    swapcheck = swapcheck+1;
                    Console.WriteLine("  This check for swap -->"+swapcheck);
                    if (num[i]>num[j])
                    {
                        swapcount=swapcount+1;
                        int temp;
                        temp = num[i];
                        num[i] = num[j];
                        num[j] = temp;

                        Console.WriteLine("         This is swap count------->"+swapcount);

                        //minIndex = j;

                    }

                }
                
            }
        }

        static void PrintSortedItems()
        {
            for (int i = 0; i < num.Length; i++)
            {
                Console.WriteLine(num[i]);
            }
        }
    }
}

The complete .NET core project is available in this Github repository https://github.com/sundarnarasiman/SortingAlgorithms

Execution and Results

This is pass number —–>1
This check for swap –>1
This is swap count——->1
This check for swap –>2
This is swap count——->2
This check for swap –>3
This check for swap –>4
This is swap count——->3
This check for swap –>5
This check for swap –>6


This is pass number —–>2

This check for swap –>7
This is swap count——->4
This check for swap –>8
This check for swap –>9
This is swap count——->5
This check for swap –>10
This is swap count——->6
This check for swap –>11


This is pass number —–>3
This check for swap –>12
This is swap count——->7
This check for swap –>13
This is swap count——->8
This check for swap –>14
This is swap count——->9
This check for swap –>15
This is swap count——->10


This is pass number —–>4

This check for swap –>16
This is swap count——->11
This check for swap –>17
This is swap count——->12
This check for swap –>18
This is swap count——->13


This is pass number —–>5
This check for swap –>19
This is swap count——->14
This check for swap –>20
This is swap count——->15


This is pass number —–>6
This check for swap –>21
This is swap count——->16


Printing sorted array
1
2
3
5
6
7
8

Summary

For sorting 7 items, it took 6 passes, 21 checks for swaps and 16 actual swaps. Again, the number of swaps and swap checks are completely dependent on how the elements are arranged in the array. This is not the best performing sorting algorithm. This has the worst case complexity of O(n^2).

Bubble Sort Algorithm C#

Bubble Sort is one of the simplest Sort Algorithms to implement, at the same time it’s not the most efficient.

Overview

We try to compare ‘i’ the element and ‘i+1’ the element in the array of numbers to be sorted. If ‘i’ th element is greater than ‘i+1″, we swap the position of these two numbers in the array. We keep on going next in the array and complete the check and swapping unitil ‘n-1’ and ‘n’ the element. This complete round is called a pass. We try do up to n-1 passes (check and swap) until all the numbers are sorted. This is for sorting in ascending order.

Pseudocode

// Outer loop for n-1 passes

static int [] num = {numbers to be sorted}

For (int k=0;k<n-1);k++)

{

for (int i=0;i<n-k-1;i)

{

if (num[i] > num [i+1])

{

Do a swap

}

}

}

n – size of the array (num.length)

Implementation in C#

The complete code is C# is below.

using System;

namespace BubbleSort
{
    class Program
    {
         static int [] num = {7,6,5,4,3,2,1};
         static int swapcount = 0;
        static void Main(string[] args)
        {
           
            // Total number of passes for swap it is 0 to arr.length-1
           for (int k=0;k<num.Length-1;k++)
           {
               int passcount = k+1;
                Console.WriteLine("This is "+"pass number-----> "+passcount);
                PassAndSwap(num,k);
            }
          // PrintSortedArray(num);
            Console.WriteLine("Hello World!");
        }



        public static void PassAndSwap(int [] input, int pass)
        {
            // Total number of swaps = 0 to arr.length-swap_iteration-1
            for (int i=0; i<input.Length-pass-1;i++)
            {
                

                if (input[i] > input[i+1])
                {
                    swapcount = swapcount+1;
                Console.WriteLine("     This is "+ "swap number ---> "+ swapcount);
                    int temp;
                    temp = input[i];
                    input[i]=input[i+1];
                    input[i+1]=temp;
                   
                }
            }
            PrintSortedArray(num);

        }

       
           
        

        public static void PrintSortedArray(int [] Sorted)
        {
            
            for (int j = 0 ;j<Sorted.Length;j++)
            {
                Console.Write(Sorted[j]+",");
               
            }
             Console.WriteLine("\n");

        }
    }
}

The link for Github repo is https://github.com/sundarnarasiman/SortingAlgorithms/tree/main/BubbleSort

Execution and Output

When we execute the above code we’ll get this output below. For sorting 7 (n) numbers, we can clearly see that this is doing 6 (n-1 passes.

This is pass number—–> 1
This is swap number —> 1
This is swap number —> 2
This is swap number —> 3
This is swap number —> 4
This is swap number —> 5
This is swap number —> 6
6,5,4,3,2,1,7,

This is pass number—–> 2
This is swap number —> 7
This is swap number —> 8
This is swap number —> 9
This is swap number —> 10
This is swap number —> 11
5,4,3,2,1,6,7,

This is pass number—–> 3
This is swap number —> 12
This is swap number —> 13
This is swap number —> 14
This is swap number —> 15
4,3,2,1,5,6,7,

This is pass number—–> 4
This is swap number —> 16
This is swap number —> 17
This is swap number —> 18
3,2,1,4,5,6,7,

This is pass number—–> 5
This is swap number —> 19
This is swap number —> 20
2,1,3,4,5,6,7,

This is pass number—–> 6
This is swap number —> 21
1,2,3,4,5,6,7,

The number of swaps depends on how these numbers are arranged in the array.

Time Complexity

When it comes to time complexity, this is not the best performing sorting algorithm. The time complexity in worst case is O(n^2). We’ll see another sorting algorithm in another post.

AWS DevAx::connect Webinar series – June 2021

We know our developer community is continuously looking for new ways to innovate, build and scale their businesses. Join us for AWS DevAx::connect Webinar Series, a 4-day technical walk through sessions with live demos for developers to learn and build on AWS.

Event Schedule

·       Tuesday, June 1, 2021: Building scalable and maintainable infrastructure with the AWS CDK

·       Thursday, June 3, 2021: Accelerate idea to implementation of Microservices using AWS Copilot

·       Tuesday, June 8, 2021: CI/CD with AWS proton for containers

·       Thursday, June 10, 2021: Build GraphQL enabled applications using Amazon AppSync

Check the full agenda here

Why Attend?

 Whether you are an early-stage developer or have an advanced proficiency level, this series caters to everyone and will show you how to modernize your applications like an expert!

Learn through interactive presentations, live demos and technical insights from AWS experts.

Get your queries answered through Live Q&A session with the experts.

Presenters

  • Mohammed Fazalullah Qudrath, Developer SA – ASEAN, AWS
  • Sundararajan Narasiman, SA – Developer Specialist, AISPL
  • Anitha Deenadayalan, Specialist SA, Dev Readiness, AWS

Join us for AWS DevAx::connect series

WSL2 apt update not working

I have recently set up Windows Subsystem for Linux (WSL2) on my Windows 10 laptop and installed Ubuntu 20.04 LTS. When i tried ‘apt update’ on Ubuntu distro, it failed with following error messages.

> sudo apt-get update
Err:1 http://security.ubuntu.com/ubuntu bionic-security InRelease
  Temporary failure resolving 'security.ubuntu.com'
Err:2 http://archive.ubuntu.com/ubuntu bionic InRelease
  Temporary failure resolving 'archive.ubuntu.com'
Err:3 http://archive.ubuntu.com/ubuntu bionic-updates InRelease
  Temporary failure resolving 'archive.ubuntu.com'
Err:4 http://archive.ubuntu.com/ubuntu bionic-backports InRelease
  Temporary failure resolving 'archive.ubuntu.com'

I did the following to get it working.

Step #1.

On the Ubuntu distro, create a file at this location /etc/wsl.conf.

The file should have the following configuration.

[network]
generateResolvConf = false

If we don’t set this file, WSL will automatically load a default /etc/resolv.conf with default namesever configuration.

Shut down and restart the distro.

Step #2

Delete the default /etc/resolv.conf file.

sudo rm /etc/resolv.conf

Create a new /etc/resolv.conf with the following entry.

nameserver 8.8.8.8

Now, restart the WSL2 and open the distro again. The apt update on WSL2 should work like a charm.

How to set up AWS Copilot on Windows Subsystem for Linux

AWS Copilot is an open source command line interface that makes it easy for developers to buildrelease, and operate production ready containerized microservices on Amazon ECS and AWS Fargate. AWS Copilot provides a simple declarative set of commands, including examples and guided experiences built in to help customers deploy quickly. After writing your application code, Copilot automates each step in the deployment lifecycle including pushing to a registry, creating a task definition, and creating a cluster.

Default application types are provided for new applications based upon AWS best practices to increase developer productivity and simplify running containers in the cloud. All you need to spin up production ready services is AWS Copilot, an AWS account, and your code.

You can install AWS Copilot on Linux, Mac OS and Windows 10. The detailed instructions for the installation is available here.

If you want to natively run AWS Copilot on Windows 10, there is an .exe file for installation in the above mentioned link. In this post, i will walkthrough on how to set up AWS Copilot on Windows Subsystem for Linux (WSL2.

Step1 – Install WSL2 on Windows 10.

I breifly convered this in one of my other post. You can refer this official documentation for details

Step 2 – Install Docker Desktop on Windows by leveraging WSL2 backend

Again, i briefly covered this in one of my previous post. You can refer this official documentation for details.

Step 3 – Install build essential package on WSL2 distro

sudo apt install build-essential

Step 4 – Install and configure AWS CLI on WSL2 distro

sudo apt install awscli

Step 5 – Install Docker on WSL2 Distro

sudo apt install docker.io

Step 6 – Ensure Docker engine on Windows 10 host leverages WSL2 Distro

Step 7 – Install AWS Copilot on WSL2 distro

curl -Lo copilot https://github.com/aws/copilot-cli/releases/latest/download/copilot-linux && chmod +x copilot && sudo mv copilot /usr/local/bin/copilot && copilot --help

Step 8 – Containerize and run a sample micro-service

git clone https://github.com/aws-samples/aws-copilot-sample-service.git
cd aws-copilot-sample-service
copilot init

Copilot would interact with you with guided questions to initialize the configuration for the micro-service.

copilot svc deploy

Copilot will set up the following resources in your AWS account.

  • A VPC
  • Subnets/Security Groups
  • Application Load Balancer
  • Amazon ECR Repositories
  • ECS Cluster & Service running on AWS Fargate

Once the deployment is complete, you should see this public load balanced service up and running.

This completes the steps for setting up AWS Copilot on Windows Subsytem for Linux.

Install Docker Desktop on Windows 10 using WSL2 backend

Nowadays, Docker is the most widely used container runtime for building and running containerized applications/micro-services. The Docker Desktop for Windows is a compelling package that comes with Docker Engine, Docker CLI client, Docker Compose, Notary, Kubernetes and CredentialHelper. In Windows 10, you can install Docker Desktop for Windows and run containers in two modes – Windows Containers mode and Linux Container mode.

I followed the steps in this article to get going. There are two options for setting up Docker on Windows – one using WSL2 back-end and other using hyper-v backend.

In this post, i’m leveraging WSL2 back-end. For leveraging WSL2 backend, Linux kernel update package needs to be installed. Download and run the Docker Desktop install after meeting all the pre-requisistes in the above mentioned article. For setting up WSL2 on Windows 10, you can refer my other blog post.

After successful installation of Docker Desktop for Windows, Log out and Log in back.

The Docker is started automated.

Now I can pull a container image from Powershell terminal.

I can also run the same image from WSL2 terminal.

Thus WSL2 provides seamless integration with Windows 10.

Install WSL2 on Windows 10

I’m a big fan of Windows Subsystem for Linux on Windows 10. I use WSL terminal as the default shell for lot of software development activities. I followed the following steps mentioned in this article Install WSL on Windows 10 | Microsoft Docs to install WSL2 on my Windows 10 (OS Build 19042.928).

Step 1 – Enable the Windows Subsystem for Linux

dism.exe /online /enable-feature /featurename:Microsoft-Windows-Subsystem-Linux /all /norestart

Step 2 – Enable Virtual Machine feature

Enable Virtual Machine Platform (an optional feature) before installing WSL2.

dism.exe /online /enable-feature /featurename:VirtualMachinePlatform /all /norestart

If you have hyper-v enabled, disable that. If you don’t disable hyper-v, you won’t be able to install Linux Kernel update package in step 3.

Restart the machine to complete the installation of WSL.

Step 3 – Linux Kernel update paxckage

Download and run the following Linux Kernel update package.

https://wslstorestorage.blob.core.windows.net/wslblob/wsl_update_x64.msi

If you have hyper-v windows feature enabled, you won’t be able to install this package.

Step 4 – Set WSL 2 as default version

wsl --set-default-version 2

Step 6 – Install required Linux Distro.

In this case, i’m installing Ubuntu 20.0.4 by navigating to WSL store.

This completes the installation of WSL2 on Windows 10.

Access denied while accessing ELB using role “arn:aws:iam::role/aws-elasticbeanstalk-service-role

I got this error message when I tried to deploy a java sprint application using Elastic beanstalk.

When i analyze this further, it shows that the IAM policy associated with the Service Role is missing the following actions.

"elasticloadbalancing:DescribeLoadBalancers",
                "elasticloadbalancing:DescribeTargetHealth",

The IAM associated with the service role had the following configuration.

    “Version”: “2012-10-17”,

{

    “Statement”: [

        {

            “Effect”: “Allow”,

            “Action”: [

                “elasticloadbalancing:DescribeInstanceHealth”,

                “ec2:DescribeInstances”,

                “ec2:DescribeInstanceStatus”,

                “ec2:GetConsoleOutput”,

                “ec2:AssociateAddress”,

                “ec2:DescribeAddresses”,

                “ec2:DescribeSecurityGroups”,

                “sqs:GetQueueAttributes”,

                “sqs:GetQueueUrl”,

                “autoscaling:DescribeAutoScalingGroups”,

                “autoscaling:DescribeAutoScalingInstances”,

                “autoscaling:DescribeScalingActivities”,

                “autoscaling:DescribeNotificationConfigurations”

            ],

            “Resource”: [

                “*”

            ]

        }

    ]

}

To give some background, this is an auto-created Service Role. This was created by Visual Studio 2019 when i used Elastic Beanstalk for .NET applications.

The fix for this is to associate the IAM Policy ‘arn:aws:iam::aws:policy/service-role/AWSElasticBeanstalkEnhancedHealth’ with Service Role

https://docs.aws.amazon.com/elasticbeanstalk/latest/dg/concepts-roles-service.html

This turns the Elastic Beanstalk environment health to green.

Working with Github private repository using bash on Windows 10

There are times, we want to collaborate with other stakeholders in Github in a private manner. Meaning, we need to work and collaborate on a private Github repository. If you have a private Github private repository ready for collaboration, the most proven way to work with that is to leverage one of the following two options.

  1. Leverage SSH keys at the Github account level. So that you can work with Github private repository using SSH keys. The whole idea is that you will be generating an RSA key pair using SSH Key gen utility, add the private key portion of the key pair to the SSH agent and upload the public key portion of the key pair to the Github account settings. The advantage of this approach is that you have one SSH key defined at the Github account level to manage or work with all the private Github repositories created under that account.githubsshkey
  2. Leverage Deploy Keys at the individual repository level. I have learnt that a Deploy Key can be associated with only one Github repository at this point in time. githubdeploykey

The advantage of the second approach is that you can have a dedicated  key or set of deploy keys for individual repositories.

In this post, i’ll be covering the option #1. Basically i will leverage bash on windows 10 to work with private github repository using SSH keys. My windows 10 is already set up with Ubuntu 18.0.4 for Windows sub-system for linux.  I’m not covering the steps for setting up bash on Windows 10 using Windows subsystem for linux. You can refer microsoft documenation for that. Let’s move to the SSH set up process for Github.

Navigate to the directory in windows 10, where you want to generate SSH key pair.

pic1

Type ‘bash’ on the command prompt. It will launch the bash shell on windows 10. Basically the Windows folder that you have pointed will be mounted to the ubuntu 18.0.4 bash shell.

Now you can generate the SSH key pair using ‘ssh-keygen’ utility.

ssh-keygen -t rsa -b 4096 -C “your_email@example.com

Enter the name of the file for saving the key pair and provide any arbitrary passphrase when prompted.

pic2

Start the ssh on the bash shell. We need to explicty start it, because the run levels of this is different from a standard ubuntu desktop OS. I have learnt that the SSH agent does not get started automatically when you invoke bash on windows 10, unlike a standard ubuntu desktop OS.

eval $(ssh-agent -s)

pic3

Add the private key portion of the generated key pair to the SSH agent.

ssh-add keyname

If you getting a permission error for the generated key pair, the key will not get added successfully to the agent.

pic4

Even if you try to modify the permission of the key using ‘chmod 400’ or ‘chmod 600’ on the mounted directory, it won’t be successful. Becuase i’ve learnt that changing file permissions using chmod on the mounted directory (from windows 10) does not work.

The best way to fix this is to copy the key to a folder under the ubuntu user root directory, not to any windows mounted directory on bash.

Check if the directory ~/.ssh already exists on the bash shell. If not, explicitly create a directory ~/.ssh and exit the bash shell.

Again, navigate to the directory in windows 10 where the key pairs are generated and launch bash from there.

copy private key to ~/.ssh

pic5.JPG

Navigate to ~/.ssh and change permissions using any one of the following commands.

chmod 400 sundargitsshkey

chmod 600 sundargitsshkey

pic6

Copy the public key of the generated key pair (with ‘.pub’ suffix) to New –> SSH Key under Github account settings. Basically copy the content of the public key using any of the text editors and paste there in textbox available in New –> SSH Key under Github account settings.

Navigate to the SSH config file located in ‘/etc/ssh/ssh_config’ and add an entry for ‘IdentityFile ~/.ssh/sundargitsshkey’

sudo nano ssh_config

pic7

Start the SSH agent explicitly.

eval $(ssh-agent -s)

Verify the connectivity to Github using this command ‘SSH -T git@github.com’. You need to user the Github user name as ‘git’. If you try to use your actual Github user name, you’ll get errors.

It will ask you to confirm to accept the warning on authenticity of github.com. Accept it and provide passphrase for private key file when prompted. You’ll get the confirmation for successful authentication to make SSH calls into Github account from your bash shell.

pic8

Now you do git clone, commit and push to any number of repositories under your Github account using SSH, be it a private repository or public repository. This completes the post on working with Github private repository using bash on Windows 10.