CareerCup

You mean like a reverse bfs, level by level?

logic:
BFS traversal while popping element from queue. push it on stack.

#include <queue>
#include <stack>
#include <vector>
#include "iostream"
using namespace std;

#define EOFlevel -1
 extern class Node
{
public:
	int _data;
	Node * _left;
	Node * _right;
public:
	Node(int val = 0){
		_data = val;}
};

 extern void BFSDownUp(Node * proot)
 {
	 Node* pnode = proot;
	 if(pnode == 0)
		 return;

	 queue <Node *> q;
	 stack <Node *> stk;
	 q.push(pnode);
	 q.push(new Node(EOFlevel));

	 while(!q.empty())
	 {
		 Node * ptemp = q.front();	
		 stk.push(ptemp);
		 q.pop();

		 if(q.front()->_data == EOFlevel)
		 {
			 stk.push(q.front());
			 q.pop();
		 }
		 if(ptemp->_left)
		 {
			 q.push(ptemp->_left);
		 }
		 if(ptemp->_right)
			 q.push(ptemp->_right);
		 if(stk.top()->_data == EOFlevel)
			 q.push(new Node(EOFlevel));
	 }
	 while(!stk.empty())
	 {
		 if(stk.top()->_data == EOFlevel)
		 {
			 cout << endl;
		 }
		 else
		 {
			 cout << stk.top()->_data << "==";
		 }
		 stk.pop();
	 }
 }

ahh i see.... why dont u come up onthe chat box here ... we could sync up to share stuff which i already collected

id u don't use queues....then there is no other ways else then print element of kth level in kth functil call.

PrintLevel(node* root,int CuurHeight,int DesiredHeight)
{
if(CuurHeight == DesiredHeight)
print(root->data);
else{
if(root->right != null)
PrintLevel(root->right,CuurHeight +1,DesiredHeight)
if(root->left!=null)
printLevel(root->left,CuurHeight +1,DesiredHeight)}
return;
}

//////in main()

h=height(root);

for(int i=1;i<=h;i++)
PrintLevel(root,1,i);

u will get the desired o/p

public class Tree {
public static class Node {
Object data; // TODO: Use generics
Node left;
Node right;
Node extra; // Extra pointer to link sibling
}
private Node root;
private void linkSiblings(Node curr, Node parent) {
if (curr == null) return;
if (curr.left != null && curr.right != null) {
curr.right.extra = curr.left;
linkSiblings(curr.left, curr);
linkSiblings(curr.right, curr);
} else {
Node child;
if (curr.left != null) {
child = curr.left;
} else {
child = curr.right;
}
if (parent == null) return;
Node iter = parent.extra;
while (iter != null && iter.right == null && iter.left == null) {
iter = iter.extra;
}
if (iter != null) {
if (iter.right != null) {
child.extra = iter.right;
} else {
child.extra = iter.left;
}
}
linkSiblings(child, curr);
}
}
public void linkSiblings() {
linkSiblings(root, null);
}
}

struct node {
int n;
node *left;
node *right;
};

struct list {
int n;
list * next;
};
list *hashIndex[10] = {NULL};
void printlevelwisenumbers(node **root, int n) {
node *t;
t= *root;
list *k;
if(t == NULL) {
return;
}
else {
k = (list *) malloc (sizeof(list));
k->n = t->n;
k->next = NULL;
n++;
if(hashIndex[n]) {
list *tmp;
tmp = k;
tmp->next = hashIndex[n] ;
hashIndex[n] = tmp;
}
else {
hashIndex[n] = k;
}
}

printlevelwisenumbers(&(t->left),n);
printlevelwisenumbers(&(t->right),n);

}

Should we be connecting the siblings or even the "cousins" ? If it is only siblings, then it can be done using a recursive call. But if you need to connect even the cousins, then I don't see any other way except to use a queue.

Hmm, I think that instead of a BFS a DFS can be done. DFS needs only O(h) memory where h is the height of the tree, where BFS memory consumption is O(n) where n is the number of nodes (for example one root node and very large number of children nodes with root as parent, the queue would have n-1 elements). For each DFS recursive call we remember the current height on which we currently are (starting from height 0 in root node). We do the recursive calls from parent on its children nodes from right to left. With each recursive call we increase the current height (it may be an additional argument). Assuming we're on height H and we're visiting node N and we have a map<int, vector<Node*> > connected_siblings: we do connected_siblings[H].push_back(&N); After this DFS traversal connected_siblings[0] has the root node, connected_siblings[1] has all the siblings (together with cousins) on level 1 and so on. Size of the map is O(n) but we don't copy the nodes content, they may be potentially very big, only the pointers.

Ok, it can be done in constant time, the trick is to use the list structure that is being currently build as a queue for BFS traversal, to do that we need a marker which points to a node on the list that is being built which will tell us which node in the BFS traversal we are currently visiting. Solution in C++:

struct Node
{
    int value;
    std::vector<Node*> children;
};

void link(const Node& root, std::list<Node*>& out)
{
    out.push_back(const_cast<Node*>(&root));
    std::list<Node*>::iterator marker = out.begin();

    while (marker != out.end())
    {
        Node& node = *(*marker);
        for (int i = node.children.size() - 1; i >= 0; --i)
        {
            out.push_back(node.children[i]);
        }
        marker++;
    }
}

Is it a general tree or the binary tree?
What is the the structure of the tree?If the extra pointer is there or not?
Please clarify.