Print a binary tree in an m*n 2D string array following these rules:
m
should be equal to the height of the given binary tree.n
should always be an odd number.""
.Example 1:
Input: 1 / 2 Output: [["", "1", ""], ["2", "", ""]]
Example 2:
Input: 1 / \ 2 3 \ 4 Output: [["", "", "", "1", "", "", ""], ["", "2", "", "", "", "3", ""], ["", "", "4", "", "", "", ""]]
Example 3:
Input: 1 / \ 2 5 / 3 / 4 Output: [["", "", "", "", "", "", "", "1", "", "", "", "", "", "", ""] ["", "", "", "2", "", "", "", "", "", "", "", "5", "", "", ""] ["", "3", "", "", "", "", "", "", "", "", "", "", "", "", ""] ["4", "", "", "", "", "", "", "", "", "", "", "", "", "", ""]]
Note: The height of binary tree is in the range of [1, 10].
We start by initializing a array with the dimensions being x. Here, refers to the number of levels in the given tree. In order to fill this array with the required elements, initially, we fill the complete array with ""
. After this we make use of a recursive function fill(res, root, i, l, r)
which fills the array such that the current element has to be filled in row, and the column being the middle of the indices and , where and refer to the left and the right boundaries of the columns in which the current element can be filled.
In every recursive call, we do as follows:
\nIf we\'ve reached the end of the tree, i.e. if root==null, return.
\nDetermine the column in which the current element() needs to be filled, which is the middle of and , given by say, . The row number is same as . Put the current element at .
\nMake the recursive call for the left child of the using fill(res, root.left, i + 1, l, (l + r) / 2)
.
Make the recursive call for the right child of the using fill(res, root.right, i + 1, (l + r + 1) / 2, r)
.
Note, that in the last two recursive calls, we update the row number(level of the tree). This ensures that the child nodes fit into the correct row. We also update the column boundaries appropriately based on the and values.
\nFurther, to determine the also, we make use of recursive funtion getHeight(root)
, which returns the height of the tree starting from the node. We traverse into all the branches possible in the tree recursively and find the depth of the longest branch.
At the end, we convert the array into the required list format, before returning the results.
\n\nComplexity Analysis
\nTime complexity : . We need to fill the array of size x. Here, refers to the height of the given tree.
\nSpace complexity : . array of size x is used.
\nAlgorithm
\nWe can also solve the problem by making use of Breadth First Search\'s idea. For this, we make use of a class which stores the parameters of a of the tree, including its value, its level in the tree(), and the left() and right() boundaries of the columns in which this element can be filled in the result to be returned.
\nWe start by initializing a array as in the previous approach. After this, we add the parametrized of the tree into a . After this, we do the following at every step.
\nRemove an element, $$p$, from the front of the .
\nAdd this element at its correct position in the array given by . Here, the values , and refer to the column/level number, and the left and right boundaries permissible for putting the current node into . These are obtained from the node\'s parameters, which have been associated with it before putting it into the .
\nIf the left child of exists, put it at the back of the , in a parametized form, by appropriately updating the level as the next level and the boundaries permissible as well.
\nIf the right child of exists, put it at the back of the , in a parametized form, by appropriately updating the level as the next level and the boundaries permissible as well.
\nContinue steps 1. to 4. till the becomes empty.
\nAt the end, we again convert the array into the required list format, before returning the results.
\n\nComplexity Analysis
\nTime complexity : . We need to fill the array of size x. Here, refers to the height of the given tree.
\nSpace complexity : . array of size x is used.
\nAnalysis written by: @vinod23
\n