Author: algomaster

1

Level Order Traversal of Binary Tree

Posted on by algomaster

Problem: Level order traversal of binary tree.

eg.

Level Order Traversal

Logic:

In level order traversal nodes of tree are traversed level-wise from left to right. Like depth first traversals ( Inorder,preorder and postorder traversal) level order traversal is not easily implemented recursively because each node stores address of its left and right children.

Queue data structure is used to store nodes level wise so that  each node’s children are visited. How we are going to use queue then?

We will first add root in queue. We will use a marker node and when marker node present at the start of queue, all nodes at that level are completed. As at level 0 only root presents, add marker node after that. Now until queue does not contain only marker node we will repeat following steps:

1. De-queue node present at the start of queue.

2.Add children of that node in queue if present.

3. If at the start of queue marker node present, that means we completed visiting all nodes at previous node. So de-queue marker node from start and again en-queue it. En-queue marker node again to make sure that all nodes at this level are completely accessed.

4. If queue only contains marker node that means all children are traversed that means all nodes are traversed.

Implementation:

Complexity: As all nodes of tree are visited in traversal, time complexity is O(n).

0

Binary Search Tree

Posted on by algomaster

A binary tree is a Binary Search tree if and only if:

  • All values in left subtree of a node are less than value in node.
  • All values in right subtree of a node are greater than value in node.

For eg.

Binary Search tree

1.Insert value in a binary search tree:

While inserting a new value in a binary search tree only left or right subtree is traversed from root by comparing value of root with new value.

If new value is less than root then add it to the left subtree of root else add to right subtree of root. This can be done easily using recursion.

New node always inserted at the end of a existing tree, so while inserting number of nodes traversed depends on the height of a binary tree.

 2. Delete a value from binary search tree:

When a value is less than root then left subtree of root is traversed and if present, deleted from tree. If value to be deleted is greater than root, then right subtree of root is traversed and if present value is deleted.

If value to be deleted is present in tree then there are 3 possible scenarios:

1. Value present in a leaf node of a tree.

2. Node with that value has one child (either left or right).

3. Node with that value has both children.

If node to be deleted is a leaf node then we remove that node by assigning null value to the appropriate child pointer of its parent.

If that node has only one child then we replace that node with its existing child.

If node have both children, then we need to make sure that after deleting node, binary search tree properties are maintained. So to make sure that we can either select maximum value from left subtree of that node or select minimum value from right subtree of that node and replace it with node to be deleted.

If  value to be deleted is present in a leaf node or in worst case it does not present in a tree, in both cases number of nodes traversed in this case depends on a height of a tree.

3. Validate if given binary tree is binary search tree or not:

If for all the nodes in a binary tree, binary search tree constraints(Value in node always greater than values in its left subtree and value in a node always less than values in its right subtree)  are satisfied then that tree is a binary search tree.

Validating binary search tree can be done in a recursive way.  For each root value, we are checking if that value is in between range[min,max].  For root of a tree min value is Int Min value and max value is Int Max value.

For a node in a left subtree of a node, minimum value is a Int Min value but maximum value is value present in its parent. As we know,values in left subtree of a node always less than value in node in binary search tree.

For a node in a right subtree of a node, minimum value is a value present in its parent and maximum value is Int max. As we know, values in right subtree of a node are always greater than value in node in binary search tree.

While checking if tree is binary search tree or not, all nodes a tree are traversed so complexity is O(n).

0

3Sum

Posted on by algomaster

Problem:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

eg.  Given array  S ={-1,0,1,2,-2,-1,-4}

Then solution set is: (-1,0,1), (-2,0,2),(-1,-1,2)

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (i.e, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.

Logic:

To satisfy both constraints i.e. elements in triplet must be in non-descending order and no duplicate triplets, we will sort elements in array first.

We will keep first pointer at start of array, second pointer next to first pointer and third pointer at the end of array.  For each first pointer we will find a pair with it ,which in turn form a triplet whose sum is 0.

If sum is greater than 0 then we will decrease last pointer position and if sum is less than 0 then we will increment second pointer.

We need to make sure pairs are not repeated that means if numbers are repeated in array, we should skip them by increment and decrement of pointer appropriately.

Implementation:

Complexity:  O(n2)

0

Delete value from singly linked list

Posted on by algomaster

Problem:

Given a Linked List of Integers Delete all nodes that have value x.

Logic:

The basic thing we need to take into consideration is that given value can be present in a linked list more than once. So we will traverse to complete list while deleting a value. To keep a track if value is deleted from linked list or  if  value is not present in list, we will maintain a flag variable.

There are three spots from where you can delete the given node :

1) Node to delete is the first node :

Just assign current Head’s next as Head and delete the head ! 😀

It is possible that newly made head node also contains a same value(val that is to be deleted), eg. list [1,1,3] that is why we are checking head value repeatedly until its other that given val or head becomes null.

2) Node to delete is last node :

If given value is present in last node then we just need to make, next value of its previous node ‘null’.

3) Neither last nor first (Intermediate Node) :

Consider this linked list x->y->z and you want to delete y, then to delete y ,

x.next becomes z and y.next becomes null;

 

 

Below is implementation of this logic:

As all the nodes of linked list are traversed, time complexity of this operation is O(n).

0

Basic operations on Singly Linked List

Posted on by algomaster

We will discuss basic operations on singly linked list. Operations like insert,delete and print.

1. Insert:

In singly linked list, last node stores next address value as null. So while inserting new node , linked list is traversed from start to end.

New node will be inserted at the end so last node’s next address will be pointed to new node.

As all nodes are visited while inserting new value, time complexity for this operation is O(n).

2. Insert at specific position:

Given a value and position where you want to insert. First traverse through linked list until we get node previous to desired position and then insert node at that position. In this problem we also need to check if given position is out of range of given linked list. For example, currently linked list contains only 4 nodes and for new value position is given as 10, which is incorrect.

In this case best case is insert value at start, for this time complexity will be O(1) and worst case is insert at last position or position is out of range, in this scenario all nodes of linked list will be traversed so time complexity will be O(n).

3. Delete node from at specific position:

Given position at which you want to delete a node . First traverse through linked list until we get node previous to desired position and then delete node at that position. In this problem we also need to check if given position is out of range of given linked list. For example, currently linked list contains only 4 nodes and position is given as 10, which is incorrect.

In this case best case is delete node at position 0 which is head of linked list , for this time complexity will be O(1) and worst case is delete  last node or position is out of range, in this scenario all nodes of linked list will be traversed so time complexity will be O(n).

4. Print all linked list values:

This is a simple operation on a linked list.

As all nodes are visited to print values, time complexity of this operation is O(n).

You can find solution to more problem on linked list here.

0

Check if Singly Linked list has a cycle

Posted on by algomaster

Problem:

Checking if linked has a cycle . This means that there will be no ‘null’ value for address pointer in linked list.

Logic:

I.  Without extra space solution:

If  linked list has a cycle then there never going to be a null node. So it is important to decide exit condition from loop carefully.

We will assign two nodes, one to head and one to head next. If there is cycle, then there will be a point where both temporary nodes will be pointing to same node and if there is no cycle then one of them(tempNode2 because it is assigned to next to tempNode1 at start) will become null.

Time complexity for this solution is O(n)

When cycle is present in linked list then tempNode1 traverse at the max n nodes and tempNode2 will traverse through linked list faster than tempNode1 and will examine n nodes.  If cycle not present in Linked list then tempNode2 will become null after traversing n nodes. So time complexity of this solution is O(n).

II.Using extra list:

In this solution we will create a list and will add each node to the list if its not already present in that list. We will continue adding node till tempNode is not null.

This solution uses extra space so not feasible for long linked list.

Each new node will be compared with all its previous nodes. So for ‘n’ node there will be ‘n-1’ comparisons. So time complexity of this solution is O(n).

Space complexity of this solution is O(n).