java - Binary search tree level order with parent node -

hi trying print out level order of binary search tree in format (node element, parent node element). using queues level order having hard time getting parent node. possible queues? if how go doing it? if not more optimal way of doing it? thank you!

for example following tree:

         6        /   \       5     7 

level 0: (6, null)

level 1: (5, 6) (7, 6)

so unfortunately there isn't way of doing strictly 1 queue, assuming nodes have left,right, , value. problem once depths > 0, nodes @ level might have different parents, , information gone unless store in fashion.

the easy way add node parent inside of node class. barring that, make inner class holds mapping of node parent node, or use number of data structures. below included how hashmaps.

public void printlevelorder(){     queue<node> q = new linkedlist<node>();     map<node, node> parents = new hashmap<node,node>();     node nextlevel = null;     q.add(this);     int lvl = 0;      while (!q.isempty()){         node n = q.remove();         if (n == nextlevel || nextlevel == null){             system.out.print("\nlvl " + lvl++ +" ");             nextlevel = null;         }         system.out.print("("+n.value +","+parents.remove(n)+")");         if (n.left != null){             q.add(n.left);             parents.put(n.left, n);             if (nextlevel == null)                 nextlevel = n.left;         }         if (n.right != null){             q.add(n.right);             parents.put(n.right, n);             if (nextlevel == null)                 nextlevel = n.right;         }     } } 

to print nodes level following. next level determined adding first non null nextlevel node. when have reached node, know @ start of next line, , null out again.