Recursively walk down the binary tree and build a pretty-print string. In each recursive call, a "box" of characters visually representing the current (sub)tree is constructed line by line. Each line is padded with whitespaces to ensure all lines in the box have the same length. Then th
(
root: Optional[Node],
curr_index: int,
include_index: bool = False,
delimiter: str = "-",
)
| 1885 | |
| 1886 | |
| 1887 | def _build_tree_string( |
| 1888 | root: Optional[Node], |
| 1889 | curr_index: int, |
| 1890 | include_index: bool = False, |
| 1891 | delimiter: str = "-", |
| 1892 | ) -> Tuple[List[str], int, int, int]: |
| 1893 | """Recursively walk down the binary tree and build a pretty-print string. |
| 1894 | |
| 1895 | In each recursive call, a "box" of characters visually representing the |
| 1896 | current (sub)tree is constructed line by line. Each line is padded with |
| 1897 | whitespaces to ensure all lines in the box have the same length. Then the |
| 1898 | box, its width, and start-end positions of its root node value repr string |
| 1899 | (required for drawing branches) are sent up to the parent call. The parent |
| 1900 | call then combines its left and right sub-boxes to build a larger box etc. |
| 1901 | |
| 1902 | :param root: Root node of the binary tree. |
| 1903 | :type root: binarytree.Node | None |
| 1904 | :param curr_index: Level-order_ index of the current node (root node is 0). |
| 1905 | :type curr_index: int |
| 1906 | :param include_index: If set to True, include the level-order_ node indexes using |
| 1907 | the following format: ``{index}{delimiter}{value}`` (default: False). |
| 1908 | :type include_index: bool |
| 1909 | :param delimiter: Delimiter character between the node index and the node |
| 1910 | value (default: '-'). |
| 1911 | :type delimiter: |
| 1912 | :return: Box of characters visually representing the current subtree, width |
| 1913 | of the box, and start-end positions of the repr string of the new root |
| 1914 | node value. |
| 1915 | :rtype: ([str], int, int, int) |
| 1916 | |
| 1917 | .. _Level-order: |
| 1918 | https://en.wikipedia.org/wiki/Tree_traversal#Breadth-first_search |
| 1919 | """ |
| 1920 | if root is None: |
| 1921 | return [], 0, 0, 0 |
| 1922 | |
| 1923 | line1 = [] |
| 1924 | line2 = [] |
| 1925 | if include_index: |
| 1926 | node_repr = "{}{}{}".format(curr_index, delimiter, root.val) |
| 1927 | else: |
| 1928 | node_repr = str(root.val) |
| 1929 | |
| 1930 | new_root_width = gap_size = len(node_repr) |
| 1931 | |
| 1932 | # Get the left and right sub-boxes, their widths, and root repr positions |
| 1933 | l_box, l_box_width, l_root_start, l_root_end = _build_tree_string( |
| 1934 | root.left, 2 * curr_index + 1, include_index, delimiter |
| 1935 | ) |
| 1936 | r_box, r_box_width, r_root_start, r_root_end = _build_tree_string( |
| 1937 | root.right, 2 * curr_index + 2, include_index, delimiter |
| 1938 | ) |
| 1939 | |
| 1940 | # Draw the branch connecting the current root node to the left sub-box |
| 1941 | # Pad the line with whitespaces where necessary |
| 1942 | if l_box_width > 0: |
| 1943 | l_root = (l_root_start + l_root_end) // 2 + 1 |
| 1944 | line1.append(" " * (l_root + 1)) |