Build a tree from `list representation`_ and return its root node. .. _list representation: https://en.wikipedia.org/wiki/Binary_tree#Arrays :param values: List representation of the binary tree, which is a list of node values in breadth-first order starting from the root (
(values: NodeValueList)
| 2177 | |
| 2178 | |
| 2179 | def build(values: NodeValueList) -> Optional[Node]: |
| 2180 | """Build a tree from `list representation`_ and return its root node. |
| 2181 | |
| 2182 | .. _list representation: |
| 2183 | https://en.wikipedia.org/wiki/Binary_tree#Arrays |
| 2184 | |
| 2185 | :param values: List representation of the binary tree, which is a list of |
| 2186 | node values in breadth-first order starting from the root (current |
| 2187 | node). If a node is at index i, its left child is always at 2i + 1, |
| 2188 | right child at 2i + 2, and parent at floor((i - 1) / 2). "None" indicates |
| 2189 | absence of a node at that index. See example below for an illustration. |
| 2190 | :type values: [float | int | str | None] |
| 2191 | :return: Root node of the binary tree. |
| 2192 | :rtype: binarytree.Node | None |
| 2193 | :raise binarytree.exceptions.NodeNotFoundError: If the list representation |
| 2194 | is malformed (e.g. a parent node is missing). |
| 2195 | |
| 2196 | **Example**: |
| 2197 | |
| 2198 | .. doctest:: |
| 2199 | |
| 2200 | >>> from binarytree import build |
| 2201 | >>> |
| 2202 | >>> root = build([1, 2, 3, None, 4]) |
| 2203 | >>> |
| 2204 | >>> print(root) |
| 2205 | <BLANKLINE> |
| 2206 | __1 |
| 2207 | / \\ |
| 2208 | 2 3 |
| 2209 | \\ |
| 2210 | 4 |
| 2211 | <BLANKLINE> |
| 2212 | |
| 2213 | .. doctest:: |
| 2214 | |
| 2215 | >>> from binarytree import build |
| 2216 | >>> |
| 2217 | >>> root = build([None, 2, 3]) # doctest: +IGNORE_EXCEPTION_DETAIL |
| 2218 | Traceback (most recent call last): |
| 2219 | ... |
| 2220 | binarytree.exceptions.NodeNotFoundError: parent node missing at index 0 |
| 2221 | """ |
| 2222 | nodes = [None if v is None else Node(v) for v in values] |
| 2223 | |
| 2224 | for index in range(1, len(nodes)): |
| 2225 | node = nodes[index] |
| 2226 | if node is not None: |
| 2227 | parent_index = (index - 1) // 2 |
| 2228 | parent = nodes[parent_index] |
| 2229 | if parent is None: |
| 2230 | raise NodeNotFoundError( |
| 2231 | "parent node missing at index {}".format(parent_index) |
| 2232 | ) |
| 2233 | setattr(parent, _ATTR_LEFT if index % 2 else _ATTR_RIGHT, node) |
| 2234 | |
| 2235 | return nodes[0] if nodes else None |
| 2236 |