Print binary tree in level order

© Parineeth M R

Question 17. Print the nodes of a binary tree in level order


To print the nodes of the binary tree in level order, we start with the root node and then print the child nodes in each level from left to right. Consider the binary tree below

The level order printing will result in the following output: ABCDEFG. To achieve this we make use of a queue and use the following strategy:

1. Add the root node to the queue

2. Remove the head element of the queue and print it. Then add the children of the removed element back to the queue. Repeat step-2 till the queue becomes empty.

C/C++


/*
root: root node of the tree 
q: queue that helps in printing in level order
*/
void print_level_order(struct node *root, queue<struct node*>& q)
{
	struct node *n;
	int num_nodes_in_cur_level, num_nodes_in_next_level;

	if (!root)
		return;

	/*Add the root node to the empty queue*/
	q.push(root);
	num_nodes_in_cur_level = 1;
	num_nodes_in_next_level = 0;

	/*Process the nodes in the queue in Breadth First manner*/
	while (!q.empty()) {

		/*Remove the node at the head of the queue*/
		n = q.front();
		q.pop();

		print_data(n->data); /*print the data in the node*/

		/*Add the left child to the end of the queue*/
		if (n->left) {
			q.push(n->left);
			num_nodes_in_next_level++;
		}

		/*Add the right child to the end of the queue*/
		if (n->right) {
			q.push(n->right);
			num_nodes_in_next_level++;
		}

		num_nodes_in_cur_level--;

		/*go to next line, if all nodes in current level are processed*/
		if (num_nodes_in_cur_level == 0) {
			cout << endl;
			num_nodes_in_cur_level = num_nodes_in_next_level;
			num_nodes_in_next_level = 0;
		}
	}
}



Java


/*
root: root node of the tree 
q: queue used for printing the tree 
*/
public static void printLevelOrder(TreeNode root, Queue<TreeNode> q) {
	if (root == null)
		return;

	/*Add the root node to the empty queue*/
	q.add(root);
	int numNodesInCurLevel = 1;
	int numNodesInNextLevel = 0;

	/*Process the nodes in the queue in Breadth First manner*/
	while (!q.isEmpty()) {

		/*Remove the node at the head of the queue*/
		TreeNode n = q.remove();

		printData(n.data); /*print the data in the node*/

		/*Add the left child to the queue*/
		if (n.left != null) {
			q.add(n.left);
			numNodesInNextLevel++;
		}

		/*Add the right child to the queue*/
		if (n.right != null) {
			q.add(n.right);
			numNodesInNextLevel++;
		}

		numNodesInCurLevel--;

		/*go to next line, if all nodes in current level are processed*/
		if (numNodesInCurLevel == 0) {
			System.out.println();
			numNodesInCurLevel = numNodesInNextLevel;
			numNodesInNextLevel = 0;
		}
	}
}



Python


#root: root node of the tree 
#q: Python Queue object used for printing the tree
@staticmethod
def print_level_order(root, q):
	if (not root):
		return

	#Add the root node to the empty queue
	q.put(root)
	num_nodes_in_cur_level = 1
	num_nodes_in_next_level = 0

	#Process the nodes in the queue in Breadth First manner
	while (not q.empty()) :
		#Remove the node at the head of the queue
		n = q.get()

		TreeNode.print_data(n.data) #print the data in the node

		#Add the left child to the queue
		if (n.left) :
			q.put(n.left)
			num_nodes_in_next_level += 1
		
		#Add the right child to the queue
		if (n.right) :
			q.put(n.right)
			num_nodes_in_next_level += 1
		
		num_nodes_in_cur_level = num_nodes_in_cur_level - 1

		#go to next line, if all nodes in current level are processed
		if (num_nodes_in_cur_level == 0) :
			print('')
			num_nodes_in_cur_level = num_nodes_in_next_level
			num_nodes_in_next_level = 0
		



Find if a binary tree is a binary search tree

© Parineeth M R

Question 16. Find if a binary tree is a binary search tree


The initial approach that comes to mind is to check if the left child node is smaller than the parent node and the right child node is greater than the parent node for all the nodes in the tree. However this solution will not work as shown in the binary tree above. Every node satisfies the condition that the left child is smaller than the parent and the right child is greater than the parent. But the tree is still not a binary search tree since node 9 is incorrect. To correctly find out if a tree is a binary search tree, we should traverse the tree in-order and check if the nodes are present in ascending order

C/C++


/*cur_node: current node whose left and right sub-trees need to be checked
prev_node_pp: the in-order predecessor of cur_node
Return value: 1 if the tree is a binary search tree, 0 otherwise
*/
int is_bst(struct node *cur_node, struct node ** prev_node_pp)
{
	if (!cur_node)
		return 1;

	/*Check if the left sub-tree is a BST*/
	if (!is_bst(cur_node->left, prev_node_pp)) 
		return 0;

	/*If data in cur_node is <= to previous node then it is not a BST*/
	if (*prev_node_pp && cur_node->data <= (*prev_node_pp)->data)
		return 0;

	/*Update previous node to current node*/
	*prev_node_pp = cur_node;

	/*Check if the right sub-tree is a BST*/
	return is_bst(cur_node->right, prev_node_pp); 
}



Java


/*curNode: current node 
prevNodeArray: in-order predecessor of curNode is present in prevNodeArray[0]
Return value: true if the tree is a binary search tree, false otherwise
*/
public static boolean isBst(TreeNode curNode, TreeNode[] prevNodeArray)  {
	if (curNode == null)
		return true;

	/*Check if the left sub-tree is a BST*/
	if (!isBst(curNode.left, prevNodeArray)) 
		return false;

	/*If data in curNode is <= previous node then it is not a BST*/
	TreeNode prevNode = prevNodeArray[0];
	if (prevNode != null && curNode.data <= prevNode.data)
		return false;

	/*Update previous node to current node*/
	prevNodeArray[0] = curNode;

	/*Check if the right sub-tree is a BST*/
	return isBst(curNode.right, prevNodeArray); 
} 



Python


#cur_node: current node 
#prev_node_list: prev_node_list[0] has in-order predecessor of cur_node 
#Return values: True if the tree is a binary search tree, False otherwise
@staticmethod
def is_bst(cur_node, prev_node_list):
	if (not cur_node):
		return True

	#Check if the left sub-tree is a BST
	if (not TreeNode.is_bst(cur_node.left, prev_node_list)): 
		return False

	#If data in cur_node is <= previous node then it is not a BST
	prev_node = prev_node_list[0]
	if (prev_node and cur_node.data <= prev_node.data):
		return False

	#Update previous node to current node
	prev_node_list[0] = cur_node

	#Check if the right sub-tree is a BST
	return TreeNode.is_bst(cur_node.right, prev_node_list)



Is binary tree balanced

© Parineeth M R

Question 15. Find if a binary tree is balanced


A binary tree is balanced if at every node in the tree, the absolute difference between the height of the left-subtree and the height of the right sub-tree doesn’t exceed 1. To solve the problem we recursively traverse the tree and calculate the height of the nodes in a bottom up manner. If at any node, the difference between the height of the left and right sub-trees exceeds 1, we report that the tree is unbalanced.

C/C++


/*cur_node: node of the binary tree being checked
height: height of the current node is returned here
Return value: 1 if the tree is balanced, 0 otherwise
*/
int is_balanced(struct node *cur_node, int *height)
{
	int is_left_balanced, is_right_balanced;
	int left_height, right_height;

	if (!cur_node) {
		*height = 0;
		return 1;
	}

	is_left_balanced = is_balanced(cur_node->left, &left_height);
	is_right_balanced = is_balanced(cur_node->right, &right_height);

	if (!is_left_balanced || !is_right_balanced)
		return 0;

	/*If the difference between height of left subtree and height of
	right subtree is more than 1, then the tree is unbalanced*/
	if (abs(left_height - right_height) > 1)
		return 0;

	/*To get the height of the current node, we find the maximum of the  
	left subtree height and the right subtree height and add 1 to it*/
	*height = max(left_height, right_height) + 1;

	return 1;	
}



Java


/*curNode: node of the binary tree being checked
height: height of the curNode is returned here
Return value: true if the tree is balanced, false otherwise
*/
public static boolean isBalanced(TreeNode curNode, Int height) {
	Int leftHeight = new Int();
	Int rightHeight = new Int();

	if (curNode == null) {
		height.value = 0;
		return true;
	}


	boolean isLeftBalanced = isBalanced(curNode.left, leftHeight);
	boolean isRightBalanced = isBalanced(curNode.right, rightHeight);

	if (!isLeftBalanced || !isRightBalanced)
		return false;

	/*If the difference between height of left subtree and height of
	right subtree is more than 1, then the tree is unbalanced*/
	if (Math.abs(leftHeight.value - rightHeight.value) > 1)
		return false;

	/*To get the height of the current node, we find the maximum of the  
	left subtree height and the right subtree height and add 1 to it*/
	height.value = Math.max(leftHeight.value, rightHeight.value) + 1;

	return true;	
}



Python


#cur_node: node of the binary tree being checked
#Return values: 1. True if the tree is balanced, False otherwise
#		2. height of the cur_node is also returned
@staticmethod
def is_balanced(cur_node) :
	if (not cur_node) :
		height = 0
		return True, height
	
	is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
	is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)

	#To get the height of the current node, we find the maximum of the  
	#left subtree height and the right subtree height and add 1 to it
	height = max(left_height, right_height) + 1

	if (not is_left_balanced or not is_right_balanced):
		return False, height

	#If the difference between height of left subtree and height of
	#right subtree is more than 1, then the tree is unbalanced
	if (abs(left_height - right_height) > 1):
		return False, height
	
	return True, height	



Is binary tree symmetric

© Parineeth M R

Question 14. Find if a binary tree is symmetric


A binary tree is symmetric, if the left sub-tree of each node is a mirror image of the right sub-tree. An example of a symmetric binary tree is given below

C/C++


int compare_nodes ( struct node *n1, struct node *n2) {
	if (!n1 && !n2)  /*If both the nodes are NULL */
		return 1;  /* return symmetric*/
	
	if ( (n1 && !n2) || (!n1 && n2)) /*If one node is NULL and other is not*/
		return 0; /*return not symmetric*/
	
	if (n1->data != n2->data) /*If data of two nodes don't match */
		return 0; /* return not symmetric */
		
	if (!compare_nodes (n1->left, n2->right)) 
		return 0;
	
	if (!compare_nodes (n1->right, n2->left)) 
		return 0;
	
	return 1; /*Return symmetric*/
}

/*Returns 1 if the tree is symmetric, 0 otherwise*/
int is_symmetric(struct node * root) {
	if (!root)
		return 1;
	
	return compare_nodes(root->left, root->right);
} 


Java


public static boolean compareNodes ( TreeNode n1, TreeNode n2) {
	if (n1 == null && n2 == null)  /*If both the nodes are null */
		return true;  /* return symmetric*/

	/*If one node is null and the other is not null*/
	if ( (n1 != null && n2 == null) || (n1 == null && n2 != null))  
		return false; /*return not symmetric*/

	if (n1.data != n2.data) /*If data of two nodes don't match */
		return false; /* return not symmetric */
	
	if (!compareNodes (n1.left, n2.right)) 
		return false;

	if (!compareNodes (n1.right, n2.left))
		return false;

	return true; /*Return symmetric*/
}

/*Returns true if the tree is symmetric, false otherwise*/
public static boolean isSymmetric(TreeNode root) {
	if (root == null)
		return true;

	return compareNodes(root.left, root.right);
}



Python


@staticmethod
def compare_nodes(n1, n2): 
	if (not n1 and not n2):  #If both the nodes are None
		return True  # return symmetric

	#If one node is None and the other is not None
	if ( (n1 and not n2) or (not n1 and n2)):  
		return False #return not symmetric

	if (n1.data != n2.data): #If data of two nodes don't match
		return False # return not symmetric 
	
	if (not TreeNode.compare_nodes(n1.left, n2.right)): 
		return False

	if (not TreeNode.compare_nodes(n1.right, n2.left)): 
		return False

	return True #Return symmetric


@staticmethod
#Returns True if the tree is symmetric, False otherwise
def is_symmetric(root): 
	if (not root):
		return True

	return TreeNode.compare_nodes(root.left, root.right) 



Mirror image of a binary tree

© Parineeth M R

Question 13. Convert a binary tree into its mirror image


An example of a binary tree and its mirror image is shown below.

So to convert the binary tree to its mirror image, the left child and the right child of each node in the tree should be swapped

C/C++


/*
cur_node: current node of the tree whose mirror image should be computed
*/
void compute_mirror_image(struct node *cur_node) {
	struct node *temp_node;
	
	if (cur_node) {
		/*Swap the left child and right child of the current node*/
		temp_node = cur_node->left;
		cur_node->left = cur_node->right;
		cur_node->right = temp_node;

		/*Recursively compute the mirror image */
		compute_mirror_image(cur_node->left);
		compute_mirror_image(cur_node->right);
	}
}


Java


/*
curNode: current node of the tree whose mirror image should be computed
*/
public static void computeMirrorImage(TreeNode curNode) {
	if (curNode != null) {
		/*Swap the left child and right child of the current node*/
		TreeNode tempNode = curNode.left;
		curNode.left = curNode.right;
		curNode.right = tempNode;

		/*Recursively compute the mirror image */
		computeMirrorImage(curNode.left);
		computeMirrorImage(curNode.right);
	}
}


Python


@staticmethod
#cur_node: current node of the tree whose mirror image should be computed
def compute_mirror_image(cur_node): 
	if (cur_node) :
		#Swap the left child and right child of the current node
		cur_node.left, cur_node.right = cur_node.right, cur_node.left


		#Recursively compute the mirror image 
		TreeNode.compute_mirror_image(cur_node.left)
		TreeNode.compute_mirror_image(cur_node.right)


Stack using queues

© Parineeth M R

Question 12. Implement a stack using queues


To implement a stack using queues, we have to perform the push and pop operations of the stack using the enqueue and dequeue operations supported by the queues.

A stack can be implemented using two internal queues Q1 and Q2. There are two ways to achieve this: one where the push operation is more efficient than the pop operation and the other where the pop operation is more efficient than the push operation.

Case 1: Push is more efficient than pop
When an element is pushed to the stack, the element is enqueued in Q1

When an element is popped from the stack, dequeue the first N-1 elements from Q1 (N is the number of elements currently present in Q1) and enqueue them in Q2, one element at a time. Dequeue the last element from Q1 and return it as the element popped from the stack. Now rename Q1 as Q2 and Q2 as Q1.

For instance, let us say that the elements A, B and C are added to the stack. Then A, B, C will be enqueued into Q1 as shown in the diagram below

Now if an element must be popped from the stack, dequeue A and B from Q1, then enqueue A and B in Q2. Finally dequeue the last element in Q1 which is C and return it as the popped element. Once this is done, the state of Q1 and Q2 are shown below

In the last step of the pop operation, Q1 is renamed as Q2 and Q2 is renamed as Q1 as shown below

The code for implementing a stack class using queues where push is efficient is given below

C/C++


template <class T> class StackUsingQueues 
{
	private:
	queue<T> *q1;
	queue<T> *q2;

	public:
	StackUsingQueues() { 
		q1 = new queue<T>();
		q2 = new queue<T>();
	}

	~StackUsingQueues() {
		delete q1;
		delete q2;
	}

	
	bool empty() {
		/*Stack is empty only if both queues are empty*/
		if (q1->empty() && q2->empty())
			return true;

		return false;
	}


	void push(T new_element) {
		/*Add element to the end of queue q1*/
		q1->push(new_element);
	}

 

	T pop() {
		/*If stack is empty, then throw an exception*/
		if (empty())
			throw exception();

		T e;
		/*Remove all elements from q1 and add it to q2 except the last item*/
		while (q1->size() > 1) {
			e = q1->front();
			q1->pop();
			q2->push(e);
		}

		/*Remove the last element in q1. It will contain the top of stack*/
		e = q1->front();
		q1->pop();

		/*Swap the queues q1 and q2*/
		queue<T> *temp = q1;
		q1 = q2;
		q2 = temp;

		return e; /*Return the top of the stack*/
	}

};


Java


class StackUsingQueues <T> {
	private Queue<T> q1;
	private Queue<T> q2;

	public StackUsingQueues () {
		q1 = new LinkedList<T>();
		q2 = new LinkedList<T>();
	}

	public boolean isEmpty() {
		/*Stack is empty if q1 is empty*/
		if (q1.isEmpty())
			return true;
		return false;
	}
	
	public void push(T newElement) {
		/*Add elements only to queue q1*/
		q1.add(newElement);
	}

	public T pop() {
		if (isEmpty()) 
			return null;

		/*Remove all elements from q1 and add it to q2 except the last item*/
		T e;
		while (q1.size() > 1) {
			e = q1.remove();
			q2.add(e);
		}
		
		/*Remove the last element in q1. It will contain the top of stack*/
		e = q1.remove();
 
		/*Swap q1 and q2*/
		Queue<T> temp = q1;
		q1 = q2;
		q2 = temp;
		
		return e; /*Return the top of the stack*/
	}

}



Python


#Queue in Python 2.7 has been renamed to queue. So handling this so that code
#is portable on all versions of Python
try: 
	import queue
except ImportError:
	import Queue as queue


class StackUsingQueues(object):
	def __init__(self):
		#Create the internal queues
		self.q1 = queue.Queue()
		self.q2 = queue.Queue()

	def empty(self): 
		#Stack is empty if q1 is empty
		if (self.q1.empty()):
			return True
		return False
	
	def push(self, new_element): 
		#Add elements only to queue q1
		self.q1.put(new_element)
	
	def pop(self): 
		if (self.q1.empty()):
			return None

		#Remove all elements from q1 and add it to q2 except the last item
		while (self.q1.qsize() > 1): 
			e = self.q1.get()
			self.q2.put(e)
		
		#Remove the last element in q1. It will contain the top of stack
		e = self.q1.get()

		#Swap q1 and q2
		self.q1, self.q2 = self.q2, self.q1

		return e #Return the top of the stack



Case 2: Pop is more efficient than push

When an element is pushed to the stack, the element is enqueued in Q1. All the elements of Q2 are dequeued and enqueued in Q1. Rename Q1 as Q2 and Q2 as Q1. So Q2 will always contain elements in the reverse order of insertion.
When an element is popped from the stack, a dequeue operation is performed on Q2 to obtain the element at the top of the stack.

Queue using stacks

© Parineeth M R

Question 11. Implement a queue using stacks


To implement a queue using stacks, we have to perform the enqueue and dequeue operations of the queue using the push and pop operations supported by the stacks.

Let us say that we internally use stack S1 to implement a queue. When elements are added to the queue, they are pushed onto the internal stack S1. However when we have to remove an element from the queue, if we pop the element from S1, we will be returning the most recently added element instead of the element first added to the queue. We solve this problem by using an additional internal stack S2 that stores the elements to be removed from the queue in correct order. So S2 should store the elements in reverse order of S1. By popping each element from S1 and immediately pushing it into S2, S2 will store the elements in reverse order of S1. To remove an element from the queue, we will have to just pop the element from S2.

For instance, let us say that elements A, B and C are added to the queue. Then S1 will contain A, B and C while S2 will be empty as shown in the diagram below.

Now if an element has to be removed from the queue, since S2 is empty, each element of S1 is popped and immediately pushed into S2 as shown in the diagram below.

The top of stack S2 (which is element A) is then popped to remove the element from the queue.

It is important to note that, elements should be popped from S1 and pushed into S2 only when S2 is completely empty. For instance, after A is removed, let the element D be added to the queue. D is first added to S1. Suppose D is popped from S1 and pushed to S2 even before S2 is empty, then the state of the stacks is shown below

Clearly this results in an incorrect behavior since the next element that will be removed from the queue is D as D is at the top of S2 whereas the correct element to be removed from the queue is the element B. The code for a queue class using stacks is given below:

C/C++


template <class T> class QueueUsingStacks 
{
	private:
	stack<T> s1;
	stack<T> s2;

	public:
	QueueUsingStacks() {

	}

	void add(T new_element) {
		/*Add elements only to stack s1*/
		s1.push(new_element);
	}

	T remove() {
		T e;
		if(s2.empty()) {
			/*We remove elements only from stack s2. So
			if s2 is empty, then pop all the elements from s1 and  
			push them into s2.*/
			while(!s1.empty()) {
				e = s1.top();
				s1.pop();
				s2.push(e);
			}
		}

		if (s2.empty())
			throw exception();
		
		/*If s2 is not empty, then remove the element from top of s2.
		This element corresponds to the head of the queue*/
		e = s2.top();
		s2.pop();
		return e;
	}

	bool empty() {
		/*Queue is empty only if both stacks are empty*/
		if (s1.empty() && s2.empty())
			return true;
		return false;
	}
	
};


Java


class QueueUsingStacks <T> {
	private Stack<T> s1;
	private Stack<T> s2;

	public QueueUsingStacks () {
		s1 = new Stack<T>();
		s2 = new Stack<T>();
	}

	public void add(T newElement) {
		/*Add elements only to stack s1*/
		s1.push(newElement);
	}

	public T remove() {
		T e;
		if(s2.isEmpty()) {
			/*We remove elements only from stack s2. So
			if s2 is empty, then pop all the elements from s1 and  
			push them into s2.*/
			while(!s1.isEmpty()) {
				e = s1.pop();
				s2.push(e);
			}
		}
		
		/*If s2 is not empty, then remove the element from top of s2.
		This element corresponds to the head of the queue*/
		e = null;
		if(!s2.isEmpty())
			e = s2.pop();

		return e;
	}

	public boolean isEmpty() {
		/*Queue is empty only if both stacks are empty*/
		if (s1.isEmpty() && s2.isEmpty())
			return true;
		return false;
	}
	
}


Python


#Queue in Python 2.7 has been renamed to queue. So handling this so that code
#is portable on all versions of Python
try: 
	import queue
except ImportError:
	import Queue as queue


class QueueUsingStacks(object):
	def __init__(self):
		#Create the internal stacks
		self.s1 = queue.LifoQueue()
		self.s2 = queue.LifoQueue()

	def add(self, new_element): 
		#Add elements only to stack s1
		self.s1.put(new_element)
	
	def remove(self): 
		if(self.s2.empty()) :
			#We remove elements only from stack s2. So
			#if s2 is empty, then pop all the elements from s1 and  
			#push them into s2.
			while(not self.s1.empty()) :
				e = self.s1.get()
				self.s2.put(e)
			
		#If s2 is not empty, then remove the element from top of s2.
		#This element corresponds to the head of the queue
		e = None
		if(not self.s2.empty()):
			e = self.s2.get()

		return e
	

	def empty(self): 
		#Queue is empty only if both stacks are empty
		if (self.s1.empty() and self.s2.empty()):
			return True
		return False





Interleave two linked lists

© Parineeth M R

Question 10. Interleave two linked lists


Let’s consider two linked lists, L1 having the members A->B->C->D and L2 having the members X->Y->Z. Interleaving the two linked lists will result in the single linked list A->X->B->Y->C->Z->D, wherein the first node of L2 is placed next to the first node of L1, second node of L2 is placed next to second node of L1 and so on. If the sizes of the two linked lists are m and n, then interleaving can be done in O(m+n)

C/C++


/* 
n1: head of the first linked list
n2: head of the second linked list
Return value: head of the result interleaved linked list
*/
struct node* interleave_lists( struct node *n1, struct node *n2)
{
	struct node *result,  *temp1, *temp2;

	if (!n1) {
		return n2; /*If linked list1 is empty, return n2 */
	}
	
	if (!n2) {
		return n1; /*If linked list2 is empty, return n1*/
	}
	
	/*Process the two linked lists*/
	result = n1;
	while (n1 != NULL && n2 != NULL) {
		temp1 = n1->next;
		temp2 = n2->next;

		/*Place node of second linked list next to the node 
		of the first linked list*/
		if (n1->next)
			n2->next = n1->next;
		n1->next = n2;

		n1 = temp1;
		n2 = temp2;
	}
	return result;
}


Java


/* 
n1: head of the first linked list
n2: head of the second linked list
Return value: head of the result interleaved linked list
*/
public static LinkedListNode interleaveLists( LinkedListNode n1, 
					LinkedListNode n2) {

	if (n1 == null) {
		return n2; /*If linked list1 is empty, return n2 */
	}

	if (n2 == null) {
		return n1; /*If linked list2 is empty, return n1*/
	}

	/*Process the two linked lists*/
	LinkedListNode result = n1;
	while (n1 != null && n2 != null) {
		LinkedListNode temp1 = n1.next;
		LinkedListNode temp2 = n2.next;

		/*Place node of second linked list next to the node 
		of the first linked list*/
		if (n1.next != null)
			n2.next = n1.next;
		n1.next = n2;

		n1 = temp1;	
		n2 = temp2;	
	}
	return result;
}



Python


#n1: head of the first linked list
#n2: head of the second linked list
#Return value: head of the result interleaved linked list
@staticmethod
def interleave(n1, n2):
	if (not n1): 
		return n2 #If linked list1 is empty, return n2 

	if (not n2): 
		return n1 #If linked list2 is empty, return n1

	#Process the two linked lists
	result = n1
	while (n1 and n2): 
		temp1 = n1.next
		temp2 = n2.next

		#Place node of second linked list next to the node of 
		#the first linked list
		if (n1.next):
			n2.next = n1.next
		
		n1.next = n2

		n1 = temp1
		n2 = temp2

	return result



Find cycle in Linked List

© Parineeth M R

Question 9. Find out if there is a cycle in a linked list. Also find the node where the cycle begins


We can maintain the is_visited field in each node. Initially the is_visited field in all the nodes is set to 0. When a node is traversed in the linked list, the is_visited field is changed from 0 to 1. While traversing the linked list, the moment we encounter a node whose is_visited field is already 1, we know that there is a cycle in the linked list and the cycle begins at this node. The drawback of this approach is that it uses additional memory.

To solve the problem without using additional memory, we use the following idea. Suppose two runners take part in a race, one of them being faster than the other, the faster runner will overtake the slower runner as soon as the race starts. If the race track is a loop, then later in the race, the faster runner will again meet the slower runner and overtake him. Similarly, we can traverse the linked list using a fast pointer and a slow pointer. At each step, the fast pointer is moved ahead by 2 nodes, whereas the slow pointer is moved ahead by 1 node. If there is a loop in the linked list, the two pointers will meet at a common node.

To find where the loop starts, we need to do the following: Let n1 be the fast pointer and n2 be the slow pointer. When n1 and n2 meet, initialize a third pointer n3 to point to the beginning of the linked list. So n1 is ahead of n3 in the linked list. Now ignore n2 and advance n1 and n3 one node at a time. The node where n1 and n3 meet is where the loop starts.

C/C++

/*head: first node of the linked list 
Return value: first node in loop if loop exists, NULL otherwise
*/
struct node* find_loop( struct node *head) 
{
	struct node *n1 = head, *n2 = head, *n3;
	int found_loop = 0;

	/*n1 is the fast pointer. So advance it by two steps
	n2 is slow pointer. So advance it by one step
	*/
	while (n1 != NULL) {
		n1 = n1->next;
		if (n1) {
			n1 = n1->next;
			n2 = n2->next;
		}

		/*If n1 and n2 meet then there is a loop in the linked list*/
		if (n1 == n2) {
			found_loop = 1;
			break;
		}
	}
	
	if (!found_loop)
		return NULL;

	/*Find the beginning of the loop*/
	n3 = head;
	while (n1 != n3) {
		n1 = n1->next;
		n3 = n3->next;
	}
	
	return n1;
}



Java


/*head: first node of the linked list 
Return value: first node in loop if loop exists, null otherwise
*/
public static LinkedListNode findLoop( LinkedListNode head)  {
	LinkedListNode n1 = head, n2 = head;
	boolean foundLoop = false;

	/*n1 moves fast. So advance it by two steps
	n2 is slow. So advance it by one step
	*/
	while (n1 != null) {
		n1 = n1.next;
		if (n1 != null) {
			n1 = n1.next;
			n2 = n2.next;
		}

		/*If n1 and n2 meet then there is a loop in the linked list*/
		if (n1 == n2) {
			foundLoop = true;
			break;
		}
	}

	if (!foundLoop)
		return null;

	/*Find the beginning of the loop*/
	LinkedListNode n3 = head;
	while (n1 != n3) {
		n1 = n1.next;
		n3 = n3.next;
	}

	return n1;
}



Python


#head: first node of the linked list 
#Return value: first node in loop if loop exists, None otherwise
@staticmethod
def find_loop(head): 
	n1 = n2 = head
	found_loop = False

	#n1 moves fast. So advance it by two steps
	#n2 is slow. So advance it by one step
	while (n1): 
		n1 = n1.next
		if (n1): 
			n1 = n1.next
			n2 = n2.next
	
		#If n1 and n2 meet then there is a loop in the linked list
		if (n1 == n2): 
			found_loop = True
			break
	
	if (not found_loop):
		return None
	
	#Find the beginning of the loop
	n3 = head
	while (n1 != n3):
		n1 = n1.next
		n3 = n3.next

	return n1


Find where two linked lists merge

© Parineeth M R

Question 8. Two linked lists merge at a common node. Given the heads of the two linked lists, find the node where the linked lists merge. For instance, the two linked lists ABCXYZ and PQXYZ merge at node X


Using a brute force approach, we can pick each node in the first linked list and compare it with every node in the second linked list in sequential order. If we get a match, then we have found the first common node between the two linked lists. If one linked list has m nodes and the other has n nodes, this takes O(mn) time.
However there are better techniques to solve the problem. Two approaches which can perform better than the brute force approach are described below

Approach 1: Marking the nodes
An extra field is maintained in each node to indicate if the node has been visited or not. Initially the nodes in both linked lists have the field set to 0 indicating that they have not yet been visited. The nodes of the first linked list are then traversed and the visited field in the first linked list nodes is set to 1 indicating that they have been visited. Then the nodes of the second linked list are traversed in sequential order. As soon as we encounter a node in the second linked list with the visited field set to 1, we have found the first node that is common to both the linked lists. The time taken by this approach is O(m+n) and it requires additional space in each node to store the visited field

Approach 2: Counting
The lengths of the two linked lists are first computed. Let m be the number of nodes in the longer linked list and n be the number of nodes in the shorter linked list. n1 is made to point to the head of the longer linked list and n2 is made to point to the head of the shorter linked list. The absolute difference in the lengths of the two linked lists m-n is then computed. n1 is advanced in the longer linked list by m-n nodes. Now the number of remaining nodes starting from n1 in the longer linked list is equal to the number of nodes in the shorter linked list. If n1 and n2 point to the same node, we have found the first common node. If not, we advance n1 and n2 by one node in their respective linked lists and compare them. This process is repeated till we get a match or we reach the end of the linked lists. The time taken by this approach is also O(m+n) and requires no additional space. So this approach is the preferred solution and is given below.

C/C++


/*
head1: first node of linked list1
head2: first node of linked list2
Return value: first common node between the two linked lists
*/
struct node * find_intersection_node(struct node * head1, struct node *head2)
{
	struct node *n1, *n2;
	int length1, length2, diff;

	/*Find the length of the two linked lists*/
	length1 = find_length(head1);
	length2 = find_length(head2);

	/*store head of the longer linked list in n1 and head of shorter 
	linked list in n2*/
	if (length1 >= length2) {
		n1 = head1;
		n2 = head2;
	} else {
		n1 = head2;
		n2 = head1;
	}

	/*Find the difference in length of the two linked lists. Then advance
	n1 by the difference*/
	diff = abs(length1 - length2);
	while (diff > 0) {
		n1 = n1->next;
		--diff;
	}

	/*Go on comparing the nodes in linked list1 starting from n1 and
	linked list2 starting from n2 till n1 and n2 match*/
	while (n1 && n2 && n1 != n2) {
		n1 = n1->next;
		n2 = n2->next;
	}

	/*n1 will have the common node if it exists, otherwise n1 will be NULL*/
	return n1;
}


Java


/*
head1: first node of linked list1
head2: first node of linked list2
Return value: first common node between the two linked lists
*/
public static LinkedListNode findIntersectionNode(LinkedListNode head1, 
				LinkedListNode head2) {
	/*Find the length of the two linked lists*/
	int length1 = findLength(head1);
	int length2 = findLength(head2);
	LinkedListNode n1, n2;

	/*store head of the longer linked list in n1 and head of 
	shorter linked list in n2*/
	if (length1 >= length2) {
		n1 = head1;
		n2 = head2;
	} else {
		n1 = head2;
		n2 = head1;
	}

	/*Find the difference in length of the two linked lists. Then advance
	n1 by the difference*/
	int diff = Math.abs(length1 - length2);
	while (diff > 0) {
		n1 = n1.next;
		--diff;
	}

	/*Go on comparing the nodes in linked list1 starting from n1 and
	linked list2 starting from n2 till n1 and n2 match*/
	while (n1 != null && n2 != null && n1 != n2) {
		n1 = n1.next;
		n2 = n2.next;
	}

	/*n1 will have the common node if it exists, otherwise n1 will be null*/
	return n1;
}



Python


#head1: first node of linked list1
#head2: first node of linked list2
#Return value: first common node between the two linked lists 
@staticmethod
def find_intersection_node(head1, head2):
	#Find the length of the two linked lists
	length1 = LinkedListNode.find_length(head1)
	length2 = LinkedListNode.find_length(head2)

	#store head of the longer linked list in n1 and head of 
	#shorter linked list in n2
	if (length1 >= length2) :
		n1 = head1
		n2 = head2
	else :
		n1 = head2
		n2 = head1
	
	#Find the difference in length of the two linked lists. Then advance
	#n1 by the difference
	diff = abs(length1 - length2)
	while (diff > 0) :
		n1 = n1.next
		diff = diff - 1
	
	#Go on comparing the nodes in linked list1 starting from n1 and
	#linked list2 starting from n2 until n1 and n2 match
	while (n1 and n2 and n1 != n2) :
		n1 = n1.next
		n2 = n2.next
	
	#n1 will have the common node if it exists, otherwise n1 will be None
	return n1