Spiral (ZigZag printing) Printing the Binary Tree nodes in C

This is a variant of level order printing. In level order printing we can use iterative or a queue based approach. Iterative option is still available in this one too.But we are trying to follow a non iterative approach here. Instead of a queue we will have two stacks for implementing Sprial printing (also called ZigZag printing) of the Binary Tree. First we push the root node to stack one. Then we visit both stacks and take the top item and store it in a temp variable, then we will pop the stack from which we had pushed the binary tree node. At the same time we will push into the alternate stack the children of the temporary node we had stored. On one stack we will push in right then left child order and in the other one we will be pushing in left and then right children order.

For a binary tree like below

                                         1
                                         / \
                                        2 3
                                       /\  /\
                                     4 5 6 7

 the spiral printing order will be as below:

 1
23
7654

 Below is the implementation:

	#include <stdio.h>
	#include <stdlib.h>
	#include <stack>
	using namespace std;
	typedef struct node {
	int data;
	node *left, *right;
	}node;
	void printSpiralBinary(node * root)
	{
	if (root == NULL) return;
	stack <node *> s1;
	stack <node *> s2;
	s1.push(root);
	while (!s1.empty() || !s2.empty())
	{
	while (!s1.empty())
	{
	node * temp = s1.top();
	s1.pop();
	printf("%d", temp->data);
	if (temp->right) s2.push(temp->right);
	if (temp->left) s2.push(temp->left);
	}
	printf("\n");
	while (!s2.empty())
	{
	node * temp = s2.top();
	s2.pop();
	printf("%d", temp->data);
	if (temp->left) s1.push(temp->left);
	if (temp->right) s1.push(temp->right);
	}
	printf("\n");
	}
	}
	node * newNode(int data)
	{
	node * temp = (node *)malloc(sizeof(node));
	temp->data = data;
	temp->left = temp->right = NULL;
	return temp;
	}
	int main()
	{
	node *root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);
	root->right->right = newNode(7);
	printf("Sprial level Order traversal of binary tree \n");
	printSpiralBinary(root);
	getchar();
	return 0;
	}

view raw SprialPrintBST.c hosted with ❤ by GitHub

Kadanes Algorithm for finding sub-array with maximum sum

Here is the Kadanes algorithm implementation in Python. Here we pass thru the array in a linear fashion. While we pass thru the array we keep adding the elements. As we add the elements we keep track of previous largest sum ever found. We compare the present sum with so far largest sum till we finish the entire array.

	#! /usr/env/path python
	class Solution:
	##Complete this function
	#Function to find the sum of contiguous subarray with maximum sum.
	def maxSubArraySum(self,arr,N):
	##Your code here
	if (N < 1) or (N > 1000000):
	print("error : invalid array size")
	return
	max_till_now = arr[0]
	max_ending = 0
	for i in range(len(arr)):
	max_ending = max_ending + arr[i]
	if max_ending < 0:
	if(max_ending > max_till_now):
	max_till_now = max_ending
	max_ending = 0
	elif (max_till_now < max_ending):
	max_till_now = max_ending
	return max_till_now

view raw Kadane.py hosted with ❤ by GitHub

Algorithm for inserting elements from the back of the Linked List to the elements on front of the array interleaving one node each.

Algorithm for printing reversing a array from mid element and inserting nodes between two nodes . 
For example

 -> 11 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 

should be converted to 

->11 -> 1 -> 10 -> 2 -> 9 -> 3 -> 8 -> 4 -> 7 -> 5 -> 6->null

	package midinverse;
	class Node {
	int data;
	Node next;
	Node(int val, Node link)
	{
	data = val;
	next = link;
	}
	}
	public class MidInverseJava {
	Node headNode;
	MidInverseJava()
	{
	headNode = null;
	}
	Node addNode(Node toAddNode)
	{
	if (toAddNode == null)
	{
	System.out.println("Node to be added is empty");
	return null;
	}
	if(headNode == null)
	{
	System.out.println("Linked list is empty");
	headNode = toAddNode;
	return headNode;
	}
	toAddNode.next = headNode;
	headNode = toAddNode;
	return headNode;
	}
	void printNodes(Node firstNode)
	{
	while(firstNode!=null)
	{
	System.out.print(" -> "+ firstNode.data);
	firstNode = firstNode.next;
	}
	System.out.println();
	}
	static int maxCount;
	void recursiveInsert(Node tempNode, int count)
	{
	Node slowPointer = headNode;
	if (tempNode == null)
	{
	maxCount = count;
	return;
	}
	count = count + 1;
	recursiveInsert(tempNode.next, count);
	for ( int n=0 ; n < (maxCount - count)*2; n++)
	{
	slowPointer = slowPointer.next;
	}
	Node xNode = slowPointer.next;
	slowPointer.next = tempNode;
	tempNode.next = xNode;
	if (count==1)
	slowPointer.next = null;
	}
	void midinsert()
	{
	Node slowPointer, fastPointer;
	if(headNode == null || headNode.next == null)
	System.out.println("List not length enough !");
	for ( slowPointer = headNode, fastPointer=headNode ; fastPointer.next != null ; )
	{
	slowPointer = slowPointer.next;
	fastPointer= fastPointer.next.next;
	}
	recursiveInsert(slowPointer, 0);
	}
	public static void main(String [] args)
	{
	MidInverseJava obj = new MidInverseJava();
	Node n1 = new Node(1, null);
	Node n2 = new Node(2, n1);
	Node n3 = new Node(3, n2);
	Node n4 = new Node(4, n3);
	Node n5 = new Node(5, n4);
	Node n6 = new Node(6, n5);
	Node n7 = new Node(7, n6);
	Node n8 = new Node(8, n7);
	Node n9 = new Node(9, n8);
	Node n10 = new Node(10, n9);
	Node n11 = new Node(11, n10);
	obj.headNode = n11;
	obj.printNodes(obj.headNode);
	obj.midinsert();
	obj.printNodes(obj.headNode);
	}
	}

view raw MidInverseJava.java hosted with ❤ by GitHub

Algorithm to print combinations of elements in given order (Written in Java)

This is an algorithm to print combinations of elements in an array following the lexicographic order. For example if the given array is

{ 'a', 'b', 'c', 'd'}

then the answer should be

 ab, ac, ad, bc, bd, abc, abd, acd, bcd, abcd.


 Given below is the implementation:

	package combinations;
	import java.util.*;
	import java.math.*;
	public class combPowerSet {
	//printing the charachters as per the number sent.
	void printNumber(int number, char [] items)
	{
	String digitString = Integer.toString(number);
	char [] digitStringArray = digitString.toCharArray();
	int length = digitStringArray.length;
	for ( int i=0; i<length; i++)
	{
	System.out.print(items[Character.getNumericValue(digitStringArray[i])-1]);
	}
	System.out.println();
	}
	//checking if the number follows the required pattern.
	boolean checkCondition(int number, int itemSize)
	{
	boolean validNumber = true;
	String digitString = Integer.toString(number);
	char [] digitStringArray = digitString.toCharArray();
	int length = digitStringArray.length;
	for ( int i=0; i<length; i++)
	{
	for( int j = i+1; j < length; j++)
	{
	int x = Character.getNumericValue(digitStringArray[i]);
	int y = Character.getNumericValue(digitStringArray[j]);
	if (x > itemSize-1 || y > itemSize || x > y || x==y)
	{
	validNumber = false;
	break;
	}
	}
	if (validNumber == false) break;
	}
	return validNumber;
	}
	void printCombinations(char [] items)
	{
	double maxDigit = 0;
	int itemSize = items.length;
	for(int i=1; i<=itemSize; i++)
	{
	maxDigit = maxDigit + i*Math.pow(10,itemSize-i);
	}
	for(int x=12; x<=maxDigit; x++)
	{
	if(checkCondition(x, itemSize))
	{
	printNumber(x, items);
	}
	}
	}
	public static void main(String [] args)
	{
	char [] arr = { 'a','b', 'c','d', 'e'};
	combPowerSet obj = new combPowerSet();
	obj.printCombinations(arr);
	}
	}

view raw combPowerSet.java hosted with ❤ by GitHub

Byte aligned malloc implementation

Usually when we call malloc we are returned with a address where the memory is allocated. But suppose if we want to ensure that the memory allocated is aligned with some value how can we implement such an malloc. Below is an implementation of that:

	/*
	* nMalloc.cpp
	*
	* Created on: Dec 5, 2014
	* Author: prasadnair
	*/
	#include <stdlib.h>
	#include <stdio.h>
	void * aligned_malloc(size_t size, int align) {
	/* alignment could not be less then zero */
	if (align < 0) {
	return NULL;
	}
	/* Allocate necessary memory area client request - size parameter -
	* plus area to store the address of the memory returned by standard
	* malloc().
	*/
	void *ptr;
	/* accomodating atleast one aligned memory area by adding align-1
	/ size of (void *) is added since we intent to keep the below address
	/ in p. This will be retrieved later during free
	*/
	void *p = malloc(size + align - 1 + sizeof(void*));
	if (p != NULL) {
	/* Address of the aligned memory according to the align parameter*/
	ptr = (void*) (((size_t)p + sizeof(void*) + align -1) & ~(align-1));
	/* store the address of the malloc() above the beginning of our total memory area.
	*/
	*((void**)((size_t)ptr - sizeof(void*))) = p;
	/* Return the address of aligned memory */
	return ptr;
	}
	return NULL;
	}
	void aligned_free(void *p) {
	/* Get the address of the memory, stored at the
	* start of our total memory area.
	*/
	void *ptr = *((void**)((size_t)p - sizeof(void*)));
	free(ptr);
	return;
	}
	int main ()
	{
	int align;
	for (align = 2; align < 5000000; align= align*2)
	{
	int *p = (int *) aligned_malloc (1024, align);
	// trying to see if its aligned properly by finding mode with align
	// mode operator should always return zero if memory is aligned to align
	printf (" %p %d \n", p, ((long int)p)%align);
	aligned_free (p);
	}
	return 0;
	}

view raw aligned_malloc.c hosted with ❤ by GitHub