CareerCup

What is the question? Please elaborate

Is the tree structure -

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

Do inorder Tree traversal, at each instance push root into stack.
When root becomes null print stack.

tree_traverse(node* root)
{

if(root == null && stack!= empty)
{
print stack
return;
}
s.push(root.value);

tree_traverse(root->left);
tree_traverse(root->right);
}

Here is the function:

void printV(struct node *root,int *arr,int *depth)
{
        if(root)
        {
                arr[++(*depth)]=root->data;
                printV(root->left,arr,depth);
                
                if(!(root->left || root->right))
                {
                        while((*depth)>=0)
                                printf("%d ",arr[(*depth)--]);
                }
                
                printV(root->right,arr,depth);
        }
}

Complete code: ideone.com/IAKcD

correct me where i am wrong .........i am trying to do is in O(n).....but is in O(nlgn)

int breath_left(struct node* Root)
{
	if(!Root)
		return 0;
	return max(breath_left(Root->left)+1,breath_left(Root->right)-1);
}
int breath_right(struct node* Root)
{
	if(!Root)
		return 0;
	return max(breath_right(Root->right)+1,breath_right(Root->left)-1);
}
int breath(struct node* Root)
{
	return (breath_left(root)+breath_right(root)-1);
}
void verticalAtLevel(struct node* Root,int level)
{
	if(!Root)
		return;
	if(level==1)
		printf("%d  ",Root->data);
	verticalAtLevel(Root->left,level-1);
	verticalAtLevel(Root->right,level+1);
	
	
}
void vertical_travers(struct node* Root)
{
	int breathLeft=breath_left(Root);
	int i=0;
	for(i=breathLeft;i>=(-breath_right(Root));i--){
		verticalAtLevel(Root,i);
		printf("\n");}
		
}

public void traverse_vertical(Tree tree)
    {
    	if(tree == null)
    		return;
    	
    	stack.push(tree.element);
    	traverse_vertical(tree.left);
    	while(stack.size()!=0)
    	{
    		System.out.print(stack.pop());
    	}
    	traverse_vertical(tree.right);
    	
    }

reply me if i am wrong

can some one pls elaborate the question.. i cant understand!!

Pre-order tree traversal

public class Node {

private Node right;
private Node left;
private int nodeValue;

public Node (  )
{
// a Java constructor
}

public Node leftNode() {return left;}
public Node rightNode() {return right;}
public int getNodeValue() {return nodeValue;}

}

void preOrder (Node root)
{

  if(root == null) return;
  
  root.printNodeValue();
  
  preOrder( root.leftNode() );
  preOrder( root.rightNode() ); 
  
}

int[] input = {2, 3, 4, 5, 6, 7, 8};
		boolean[] visited = new boolean[input.length];
		
		int start = input.length / 2;
		for (int i = start; i <= input.length - 1; i++) {
			System.out.println(input[i]);
			visited[i] = true;
			int j = i;
			while (j > 0) {
				j = (j-1) / 2;
				if (!visited[j]) {
					System.out.println(input[j]);
					visited[j] = true;
				}
			}
		}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.Stack;

import javax.xml.stream.events.NotationDeclaration;

/*
 * 			1
 * 		2		3
 * 	4		6		7 
 * 
 * 
 */
public class VerticalTraversal {
	static class Node {
		Node left;
		Node right;
		public int element;
	}

	static Map<Integer, List<Integer>> map = new HashMap<>();
	public static void traverseAndUpdateMap(Node tree, int verticalIndex) {
		if(tree == null){
			return;
		}
		
		List<Integer> value = map.get(verticalIndex);
		if(value == null)
			value = new ArrayList<>();
		value.add(tree.element);
		map.put(verticalIndex, value);
		
		traverseAndUpdateMap(tree.left, verticalIndex-1);
		traverseAndUpdateMap(tree.right,verticalIndex+1);
	}
	
	public static void printVerticleTraversal(Node tree) {
		traverseAndUpdateMap(tree, 0);
		List<Integer> keys = new ArrayList<>(map.keySet());
		keys.sort(Comparator.naturalOrder());
		for(int i : keys){
			List<Integer> list = map.get(i);
			for(int j : list){
				System.out.print(j + " ");
			}
		}
	}
	public static void main(String[] args) {
		Node tree = new Node();
		tree.left = new Node();
		tree.right = new Node();
		tree.left.right = new Node();
		tree.left.right.left = new Node();
		tree.left.right.left.left = new Node();
		// tree.left.right = new Node();
		// tree.right.left = new Node();
		tree.right.right = new Node();

		tree.element = 1;
		tree.left.element = 2;
		tree.right.element = 3;
		tree.left.right.element = 4;
		tree.left.right.left.element = 5;
		tree.left.right.left.left.element = 6;
		// tree.left.right.element = 5;
		// tree.right.left.element = 6;
		tree.right.right.element = 7;

		printVerticleTraversal(tree);
	}
}

This code will work for every scenario, correct me if I am wrong

I'm using the following approach and it is giving result:
1. read recursively till root.left is not null
2. print node data and if it has a right node then add it in a list
3. now read through the list
4. if it has no left right nodes then print data else call traverse method on this node again.

Please comment if this solution looks ok..

List<Node> queue = new ArrayList<Node>();

public void traverse(Node root)
{
if(root.left != null)
traverse(root.left);
System.out.print(root.data+" ");
if(root.right != null)
queue.add(root.right);
}

public void printqueue()
{
if(queue.size() == 0)
return;
if(queue.size() > 0)
{
Node t = queue.get(0);
if(t.left == null && t.right == null)

{ System.out.print(t.data);
queue.remove(0);
}
else {
traverse(t);
queue.remove(0);
}

printqueue();
}
}

public static void main(String args[])
{
Node n1 = new Node(2);
Node n2 = new Node(3);
Node n3 = new Node(4);
Node n4 = new Node(5);
Node n5 = new Node(7);
Node n6 = new Node(8);

Node n7 = new Node(6);

n1.left = n2;
n2.left = n4;
n2.right = n7;
n3.left = n5;
n3.right = n6;
n1.right = n3;
VerticalTree obj = new VerticalTree();
obj.traverse(n1);
obj.printqueue();
}