The passage of the inner spiral tree

Question

I ran into an interesting problem:

Given that the binary tree prints it in an internal spiral order, that is, first print level 1, then level n, then level 2, then n-1, etc.

For Ex: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Should Output: 1 15 14 13 12 11 10 9 8 2 3 7 6 5 4 

I thought of a solution:

• Store level items in a list
  lists [0] = [1]
  lists [1] = [2, 3]
  lists [2] = [4, 5, 6, 7]
  lists [3] = [8, 9, 10, 11, 12, 13, 14, 15]

• Scroll through the list of lists in the required order (0, n-1, 1, n-2, ...) and print. Here n is the number of levels equal to 4 in the above case.

Its spatial complexity would be O (n). I am sure that there may be a better solution for it with better complexity in space, but I cannot think if this is so. Does anyone have pointers?

Answer 1

Here's a simple solution with O(1) space and O(n * h) time, where n is the number of nodes and h is the height of the tree. Save two variables indicating the current levels to print, then print each node after traversing the tree according to a binary string whose length corresponds to the corresponding depth of the tree; go left for "0", right for "1" (for example, the leftmost node in your example has reached "000", its neighbor is at "001"). Since we need to complete no more than h iterations to print a single node, the time complexity is O(n * h) .

Here is the algorithm in a few more detailed words:

 down = 0 up = tree height while: if down > up: break else: set exp to down then up (or only one if up == down): for i = 0 to 2^exp - 1: s = binary string i, padded to exp digits traverse tree according to s if a node exists by the end of s: print node down = down + 1 up = up - 1 

I'm not sure if this will be an order of magnitude faster, but you can use the same principle that goes inside the tree, instead of starting from the root for each node: go back to “0”, flip it to “1”, then keep left to the final level and repeat recursively until the line becomes "1". For example, target level 4:

 0000 => (000)1 => (00)10 => (001)1 => (0)100...etc. 

Answer 2

You do not need to store nodes by level, you can solve the problem by saving all the nodes in the deque structure, as well as maintaining the node level in the array.

 Deque <Integer> deque = new LinkedList(); Queue <Integer> q = new LinkedList(); int[]level = new int[n];//we need to store the level of each node, n is number of node q.add(0);//Adding the root node while(!q.isEmpty()){ int node = q.deque(); for(int child : getNodeChildren(node)){ level[child] = level[node] + 1;//Keep track the level of child node q.add(child); deque.add(child);//Store the child node into the queue. } } // Print output boolean printHead = true; while(!deque.isEmpty()){ if(printHead){ int node = deque.pollFirst(); print node; //Check if we already printed every node in this current level, //if yes, we need to switch to print from the end of the queue if(!deque.isEmpty() && level[deque.getFirst()] != level[node]){ printHead = false; } }else{ int node = deque.pollLast(); print node; if(!deque.isEmpty() && level[deque.getLast()] != level[node]){ printHead = true; } } } 

Code Logic:

We keep printing from the beginning of deque , if the next node is not at the same level as the last printed node, which also means that we just printed all the elements of the current level, we need to switch to printing from the end of deque , vice versa. We continue this process until all nodes are printed.

The complexity of the space is O (n), the time complexity of O (n).

Answer 3

I would first like to thank the poster for its question and provide a practical example of how the complexity of time and spatial complexity contrast each other. Given the large amount of space, your algorithm can be extremely fast (because you can create a “state”). Conversely, if you are very limited in space, you will need to perform additional iterations to compensate for the lack of state.

It turns out that this problem is easily solved in the spatial complexity of O (n). If you are allowed to create space for the result (O (n)), there are several algorithms that can create a solution in the time complexity of O (n). One of them is published (which I like), and I also propose another, and possibly elegant, approach to solving in O (n) and in the time complexity of O (n); refer to solveOrderN () method.

The problem is how to find a solution in space complexity less than O (n). To do this, you should not be allowed to create a result space, and you are forced to work as a result within the tree space asked in the question. You are forced to change elements around.

The solution I provided - solveSubOrderN () - does not create any result space; the answer is returned in the same memory space as the question.

I was very optimistic, I could solve this problem in O (log base 2 (n)) and even in time complexity close to O (n). But after a lot of analysis, I can't get it aggressive.

When you start replacing elements, you will eventually click the “stop condition” when you return to the non-recyclable element. If this stop does not exist, you can reach O (base base 2 n). But you cannot avoid it. Therefore, in order to compensate for this, I was forced to create some space (a Boolean array) that represents the state of the element being processed.

I would like to discuss how this logical state is very different from creating space for the result / solution. When you create a solution (of n elements, size s), you create space = n * s. In this question, s is an integer. In the general case, s can be very large, which makes it an “expensive” process (and the reason that the poster created this problem). The space for the Boolean array is much smaller and even negligible as s grows (i.e., N / s approaches 0 as s grows).

It also turns out that you cannot achieve the time complexity of O (n) when the complexity of the space is less than O (n). You are forced to repeat the iteration when you fall into a stop state. But it turns out that for a binary tree the number of additional iterations is small (and each iteration should just find the next starting point).

So, let us summarize two solutions s; One has a spatial complexity of O (n) and a time complexity of O (n), but, more importantly, one that has a spatial complexity of less than O (n), with a time complexity very close to O (n).

 public class BinaryTree { public static void main(String[] args) { int treeN2[] = {1, 2, 3}; int treeN3[] = {1, 2, 3, 4, 5, 6, 7}; int treeN4[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; int treeN5[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}; int answer[] = solveOrderN(treeN5); System.out.println(Arrays.toString(answer)); solveSubOrderN(treeN5); System.out.println(Arrays.toString(treeN5)); } /** * Given a binary tree, Perform inward spiral tree traversal.<br> * With this approach, there is no space created for the result. * All manipulation is done within the original tree<br> * Some space is created (boolean[n]) to add necessary state of processing. * Space Complexity: Less than O(n), greater than log(base2)(n) * Time Complexity: Slightly greater than O(n) * @param tree Input tree */ public static void solveSubOrderN(int tree[]) { boolean complete[] = new boolean[tree.length]; Arrays.fill(complete, false); System.out.println("Solving Sub O(n); tree size="+tree.length); int n = log2Round(tree.length+1); if (n == 1) return; int o[] = getLevelOffsets(n); System.out.println("Number of levels="+n); int pos = 0; complete[0] = true; int currentValue = 0; int moves=1; while (moves < tree.length) { pos = getStartingPos(complete); currentValue = tree[pos]; tree[pos] = 0; while (true) { int nextPos = getTargetPosition(pos, o, n); int nextValue = tree[nextPos]; tree[nextPos] = currentValue; complete[nextPos] = true; currentValue = nextValue; pos = nextPos; moves++; if (currentValue == 0) break; } } } /** * Given a binary tree, Perform inward spiral tree traversal. * Space Complexity: O(n) * Time Complexity: O(n) * @param tree Input tree * @return The solution */ public static int[] solveOrderN(int tree[]) { int answer[] = new int[tree.length]; int n = log2Round(tree.length+1); int o[] = getLevelOffsets(n); System.out.println("Solving O(n); tree size="+tree.length); System.out.println("Number of levels="+n); for (int i = 0; i < tree.length; i++) { answer[getTargetPosition(i, o, n)] = tree[i]; } return answer; } /** * Search for the first unprocessed element * @param complete An array of boolean (true = processed) * @return */ public static int getStartingPos(boolean[] complete) { for (int i=0; i<complete.length; i++) { if (!complete[i]) return i; } return 1; } public static int getTargetPosition(int pos, int o[], int n) { int row = getRow(pos); int rowOrder = getRowOrder(row, n); boolean isReversed = isBottom(row, n); int posInRow = getPosInRow(pos, n); int rowOffset = getRowOffset(rowSize(row), posInRow, isReversed); return o[rowOrder]+rowOffset; } public static int getRowOffset(int rowSize, int posInRow, boolean isReversed) { if (!isReversed) return posInRow; else return rowSize-posInRow-1; } public static int rowSize(int row) { return exp(row, 2); } public static int getPosInRow(int pos, int n) { int row = getRow(pos); return pos-(exp(row,2)-1); } /** * The top n/2 rows print forward, the bottom n/2 rows print reversed * @param row Zero based row [0 to n-1] * @param n Number of levels to the tree * @return true if line should be printed forward, false if reversed */ public static boolean isBottom(int row, int n) { int halfRounded = n/2; return (row <= n-halfRounded-1) ? false : true; } public static int exp(int n, int pow) { return (int)Math.pow(pow, n); } public static double log2(int n) { return (Math.log(n) / Math.log(2)); } public static int log2Round(int n) { return (int)log2(n); } /** * For a given position [0 to N-1], find the level on the binary tree [0 to n-1] * @param pos Zero based position in the tree (0 to N-1) * @return Zero based level (0 to n-1) */ public static int getRow(int pos) { return log2Round(pos+1); } /** * For a given row [0 to n-1], find the order in which that line would be processed [1 to log base 2 n] * @param row The row in the tree [0 to n-1] * @return The order that row would be processed [0 to n-1] */ public static int getRowOrder(int row, int n) { return isBottom(row, n) ? (n-row-1)*2+1 : row*2; } public static int getRowForOffset(int row, int n) { boolean isOdd = row%2 == 1; return isOdd ? n-(row-1)/2 - 1 : row/2; } /** * Compute the offset for a given ordered row * @param n The number of levels in the tree * @return Generated offsets for each row (to keep time complexity at O(n)) */ public static int[] getLevelOffsets(int n) { int o[] = new int[n]; Arrays.fill(o, 0); o[0] = 0; int offset = 0; for (int i=0; i<n; i++) { int nextRow = getRowForOffset(i, n); o[i] = offset; offset += exp(nextRow, 2); } return o; } } 

Answer 4

You can resolve it without significant additional space, but it will need O (n). The complexity of time depends on the representation of the binary tree. If you have an array, the time complexity will be O (n), for example:

 public static void main(String[] args) { int[] binaryTree = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; int nodes = binaryTree.length; int levels = (int) Math.ceil(Math.log(nodes) / Math.log(2)); int[] increment = {1, -1}; int index = 0; for (int i = 0; i < levels; i++) { int level = (index) * levels + increment[index] * (i / 2) - index; int begin = (int) Math.round(Math.pow(2, level)); int[] range = {begin, 2 * begin - 1}; for (int j = range[index]; j != range[1 - index]; j += increment[index]) { System.out.print(" " + binaryTree[j-1]); } System.out.print(" " + binaryTree[range[1 - index]-1]); index = 1 - index; } System.out.println(); } 

If you have a binary tree with nodes defined as:

 publi class Node { Node[] children; int value; } 

The complexity of the time (without extra space) will be O (n * log (n)). Example:

 public class BinaryNode { BinaryNode[] children = {null, null}; int value; public BinaryNode(int value) { this.value = value; } private int getRecursive(int reference) { int result = value; if (reference > 1) { result = children[reference%2].getRecursive(reference/2); } return result; } public int get(int p) { int reference = 1; int p2 = p; while (p2 > 1){ reference = (reference << 1) + (p2 & 1); p2 >>= 1; } return getRecursive(reference); } private void generateLevels(int levels){ if (levels > 0){ children[0] = new BinaryNode(value*2); children[0].generateLevel(levels -1); children[1] = new BinaryNode(value*2+1); children[1].generateLevel(levels -1); } } public static BinaryNode generate(int levels){ BinaryNode result = null; if (levels > 0){ result = new BinaryNode(1); result.generateLevels(levels - 1); } return result; } public static void main(String[] args) { int levels = 5; BinaryNode btreeRoot = BinaryNode.generate(levels); int[] increment = {1, -1}; int index = 0; for (int i = 0; i < levels; i++) { int level = (index) * levels + increment[index] * (i / 2) - index; int begin = (int) Math.round(Math.pow(2, level)); int[] range = {begin, 2 * begin - 1}; for (int j = range[index]; j != range[1 - index]; j += increment[index]) { System.out.print(" " + btreeRoot.get(j)); } System.out.print(" " + btreeRoot.get(range[1 - index])); index = 1 - index; } System.out.println(); } } 

EDIT

How do you calculate h with n? Easy:

 h = log2(n) 

Therefore, the time complexity: O (n * log n) == O (n * h).

The algorithm gets the element in O (log (n)), and you need to get all (n elements), so the complexity of the result time is O (n * log (n)). And the algorithm does this without too much space.

BtreeRoot is the source binary tree, the algorithm receives all the nodes in the correct order, calculates the next level in level . level goes to the values (1, levels -1, 2, levels - 2) O (1) (log2 (n) times) At each level, the algorithm receives its m nodes: from 2^level to 2^(level +1) - 1 . the sum of all levels n (the number of nodes), Depends on the level (odd or a pair), it calculates the current position of the node from beginning to end or vice versa. Then you know the position of the current node to print. You need to take the value in an ideal binary tree, it costs Log (n).

Answer 5

Saying that your spatial complexity is <O (n), it looks like you are making an assumption about how the tree is represented, and then you cannot enlarge this view with any additional data and / or structure in your solution (i.e. O ( n)).

For my answer, I will make the assumption that the tree is complete (or at least balanced), where balanced means that the height of the tree is O (logN).

Under this assumption, we can save the tree in the heap data structure. In this structure, node data is stored in the array where the levels are located:

  [0][1][1][2][2][2][2][3][3][3][3][3][3][3][3]... 

A given location in the array will have a pointer to node data or a pointer to NULL if this node does not exist in the tree.

The volume of space in this case is O(2^L) , where L is the number of levels in the tree. In a balanced tree, L = O(log(N)) , so the size of this representation is O(N) .

Also suppose we know the size of this array, then the number of levels of the ceiling(log_2(size)) tree.

Assuming the levels go from 0...K-1 , the starting location of any level in the array is: 2^L - 1 .

Here is the pseudo-code of the algorithm.

 PrintLevel( Array<Node> heap, level) { int levelStart = power( 2, level ) - 1; int nextLevelStart = (levelStart + 1) * 2 - 1; // same as power( 2, level+1 ) - 1 for( int i = levelStart; i < nextLevelStart; i++ ) { if( heap[i] != NULL ) { print( heap[i] ); } } } SpiralPrint( Array<Node> heap ) { int lowLevel = Ceil(Log(heap.size())) - 1 int highLevel = 0 while( lowLevel >= highLevel ){ PrintLevel( heap, highLevel ); if (lowLevel > highLevel) PrintLevel( heap, lowLevel ); highLevel += 1; lowLevel -= 1; } }