Created
November 24, 2020 22:52
-
-
Save edelooff/467a3e23e280771beb9f06a745130ea7 to your computer and use it in GitHub Desktop.
Functional recursive tree creation from pre-order sequence.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Haskell functional trees: https://gist.github.com/jerbaroo/bd48ff01a9988650ec698cbce4b0f2da | |
from collections import namedtuple | |
from typing import Any, List, Optional, Tuple | |
Node = namedtuple("Node", ["value", "left", "right"], defaults=[None, None]) | |
def dfs_pre(node: Node) -> Any: | |
"""Depth-first search, pre-order sequence.""" | |
if node is not None: | |
yield node.value | |
yield from dfs_pre(node.left) | |
yield from dfs_pre(node.right) | |
def make_tree(values: List[int]) -> Optional[Node]: | |
"""Functional recursive tree-creator. | |
Each recursion peels one value entry from the start of the list and continues | |
with the rest of the list. The left and right child branches have subtly | |
different pivot values (which in the recursing call becomes the ``parent``): | |
* The left branch will extend only when new values are smaller than | |
the most recently seen value. | |
* The right branch will extend as long as the values from the sequence are | |
smaller than the parent's, at which point they should be placed to the right | |
of the parent node. | |
""" | |
def _tree( | |
values: List[int], parent: Optional[int] = None | |
) -> Tuple[Optional[Node], List[int]]: | |
if not values or (parent is not None and values[0] > parent): | |
return None, values | |
pivot, *values = values | |
left, values = _tree(values, pivot) | |
right, values = _tree(values, parent) | |
return Node(pivot, left, right), values | |
return _tree(values)[0] | |
def main(): | |
tree = Node(4, Node(2, Node(1), Node(3)), Node(6, None, Node(7))) | |
print(f"Creating simple tree: {list(dfs_pre(tree))}") | |
assert tree == make_tree(list(dfs_pre(tree))) | |
if __name__ == "__main__": | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment