Functional recursive tree creation from pre-order sequence.

functional_trees.py

# 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()