java - Recursively assigning positions to node in binary search tree -

java - Recursively assigning positions to node in binary search tree -

hello i'm looking way recursively assign positions of tree int index value of node @ position can set array.

the desired tree positions designated in level-order root position 1 (i) , left kid of @ position 2i , right kid 2i + 1 - heap structure. null children not position assigned them.

1 / \ 2 3 /\ /\ 4 5 6 7 ... [1, 2, 3, 4, 5, 6, 7. ...]

and largest position in tree should size of array. add-on of nulls "space" desired output test node values.

private int largestpos // first call: assignpositions(root, 1) assignpositions(node cur, int pos) { parent = new node; if curpos > largestpos largestpos = curpos if cur == null parent.pos = pos else current.pos = pos parent = cur if cur.left != null pos = 2 * pos assignpositions(cur.left, pos) if cur.right != null pos = 2 * pos + 1 assignpositions(cur.right, pos) }

as seek print out array first 2 values assigned correctly, so big block of nulls without values (that confirmed in tree) not in tree.

i looking figure out to the lowest degree size of array need after removals within tree.

update breadthfirstsearch array:

public key[] breadthfirsttraversal() { @suppresswarnings("unchecked") key[] keysfinal = new key[largestpos]; list<key> queue = new list<key>(); list<key> keyslist = new list<key>(); list<integer> positions = new list<integer>(); if (!isempty()) { node tempnode = root; keyvaluepair<key, value> tempkey = null; queue.add(tempnode); while (!queue.isempty()) { queue.reset(); tempkey = queue.remove(); keyslist.add(tempkey); tempnode = findkey(tempkey.getkey(), root); // adds keys in order on level in list if (tempnode.getleftchild() != null) { queue = addatend(queue, tempnode.getleftchild()); } if (tempnode.getrightchild() != null) { queue = addatend(queue, tempnode.getrightchild()); } } (int = 1; < largestpos + 1; i++) { keyslist.reset(); tempkey = keyslist.remove(); tempnode = findkey(, root); if (tempnode.getposition() == i) { keysfinal[i - 1] = tempkey; } else { keysfinal[i - 1] = null; } } } homecoming keysfinal; }

you're changing pos work on left sub-tree, want original value work on right subtree. don't alter pos, set look want in phone call assignpositions.

then again, maintain creating new nodes each 1 visit, , don't see array, there's more problem that.

java recursion tree