CareerCup

Can you give an example?

root and root->left->right are part of same column ?

I think its similar to inorder transversal of binary tree.

per_column(node *root)
{
if(root == NULL)
return(0);
while(root)
{
printf(root->data);
root = root->left->right;
}
if(root->left)
per_column(root->left);

if(root->right)
per_column(root->right);
}

What about root->right->left

Here take an extra index with everynode. traverse

Tree* Calculatevertical(Tree *root, int index)
{
if(root != NULL)
{
root->verticalIndex = index;

Calculatevertical(root->left, index-1);
Calculatevertical(root->right,index+1);

return root;
}
}

Modifying the data structure of tree might not be a feasible solution. we can store the data from traversal into our own data structure.
First calculate the min and max values. For min, dfs to leftmost node with -1 at every node. traverse to rightmost node with +1 at every node. This will give max.

Secondly, create a array of size (|min| + max). With each element holding a column of traversal.

At last, As mentioned in the above mentioned algorithm, pass index as |min| value. At every node based on its index value, add the node data to a linkedlist present at column[index] of our data structure.

For printing columnwise data, start printing column array with index from 0 to |min|+max.

Prints columns from left to right.
The variable 'maxPossibleColumns' was initialized to the total number of nodes. The optimal way is to initialize it to the maximum width of the tree as suggested by Hinax above.

#include<stdio.h>
#include<stdlib.h>

struct treeNode
{
 int data;
 struct treeNode* left;
 struct treeNode* right;
};


// List that holds the columns of the tree
struct verticalList
{
 struct treeNode* treenode;
 struct verticalList* next;
};

//Create a node of the tree
treeNode* createNode(int data)
{
	treeNode* newNode = (treeNode*)malloc(sizeof(treeNode));
	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;
	
	return newNode;
}

/* Function to push a node at the head of the list*/
/* Taken from geeksforgeeks.org */
void push(struct verticalList** head_ref, treeNode* treenode)
{
  /* allocate node */
  struct verticalList* new_node =
            (struct verticalList*) malloc(sizeof(verticalList));
 
  /* put in the data  */
  new_node->treenode= treenode;
 
  /* link the old list off the new node */
  new_node->next = (*head_ref);  
  
  /* link the old list off the new node */
  new_node->next = (*head_ref);   
 
  /* move the head to point to the new node */
  (*head_ref)    = new_node;
}

/* Function to print nodes in a given linked list */
void printList(struct verticalList* node)
{
  while(node != NULL)
  {
    printf("%d ", node->treenode->data);
    node = node->next;
  }
  printf("\n");
}

//Number of nodes in the tree.
int nodeCount(treeNode* root)
{
	if(!root) return 0;
	return 1+nodeCount(root->left)+nodeCount(root->right);
}

void fillColumnsHelper(treeNode* root, verticalList** columns, int column)
{
	if(!root) return;
	
	push(&columns[column], root);
	fillColumnsHelper(root->left,  columns, column-1);
	fillColumnsHelper(root->right, columns, column+1);
}

void printColumns(treeNode* root)
{
	int maxPossibleColumns = nodeCount(root);
	
	verticalList** columns = (verticalList**)malloc(maxPossibleColumns*sizeof(verticalList*));
	
	fillColumnsHelper(root, columns, maxPossibleColumns/2);
	
	for(int i = 0; i < maxPossibleColumns; i++)
	{
		if(columns[i]) printList(columns[i]);
	}
}

int main()
{
	treeNode* root = createNode(18);
	root->left = createNode(47);
	root->right = createNode(10);
	
	root->left->left = createNode(46);
	root->left->right = createNode(30);
	
	root->left->right->left = createNode(28);
	root->left->right->left->left = createNode(7);
	root->left->right->left->right= createNode(42);
	
	root->right->left = createNode(11);
	root->right->right = createNode(13);
	root->right->left->left = createNode(4);
	
	printColumns(root);
}

nice solution !!

maintain offset

A(0)
           
           (+1) B            C(-1)

        (+2)D  (0)E  (0)F   (-2)G

SIMILARLY, you can maintain the (offset, list ) and then print it.

Hi, I think we can calculate the index value and based on the index value we can make an entry into the hash MAP say if index of a particular node is 0 then for key "0" we can make entry of value. next time if again index is calculated to 0 then we can make another entry at key "0" as list.

typedef struct intList{
int a;
strcut intList* next
}intListVal;

map <int, intListVal*> map;

now this map is an associative array which shall contain integer as key associate to a node. this node can be created, filled int value and make part of list.

what says?? any comments?

Solution fails when I add a new node

root->left->right->left->right->right = 100;

This code is under assumption made in solution by ibnipun10 dated August 10, 2010.
//Initial call: printTreesColumns(tree.getRoot());

public static void printTreesColumns(Node root)
	{
		ConcurrentHashMap<Integer, LinkedHashSet<Node>> map = new ConcurrentHashMap<Integer, LinkedHashSet<Node>>(); // concurrent collection because we are adding new keys during iterating the same; else would throw ConcurrentModificationException
		//This map consists of Integer as key which would determine the column of elements; linkedhashset would represent set of elements in that column
		LinkedHashSet<Node> set = new LinkedHashSet<Node>();
		set.add(root);
		map.put(1, set);

		LinkedHashSet<Node> tmpSet = null;
		boolean flag = false;
		int temp = 0;

		loop:
			while(true)
			{
				Set<Integer> keys = map.keySet(); //get keys of map

				for(Integer i: keys) //iterating keys of map
				{
					for(Node n : map.get(i)) //iterating set of nodes in that key
					{
						if(n.getLeft()!=null) //if left element available
						{
							temp = i-1;
							if((tmpSet=map.get(temp))==null) //if key is not available in map
							{
								tmpSet = new LinkedHashSet<Node>();
								flag = tmpSet.add(n.getLeft()); // creating new set and add element
								map.put(temp, tmpSet); //add new set in new key
							}
							else
							{
								flag = tmpSet.add(n.getLeft()); //else add element in set in given key in a map
							}
						}

						if(n.getRight()!=null) //if right element is available
						{
							temp = i+1;
							if((tmpSet=map.get(temp))==null)
							{
								tmpSet = new LinkedHashSet<Node>();
								flag = tmpSet.add(n.getRight());
								map.put(temp, tmpSet);
							}
							else
							{
								flag = tmpSet.add(n.getRight());
							}
						}
					}
				}

				if(flag) //if element was added in map's set, continue over. Else break out.
					continue loop;
				else
					break;
			}

		System.out.println("---------------------");
		Set<Integer> keys = map.keySet();
		for(Integer i: keys)
		{
			System.out.print("KEY "+i+":");
			tmpSet = map.get(i);
			for(Node n: tmpSet)
				System.out.print(n.getValue()+" ");

			System.out.println();
		}
	}