Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Functional recursive tree creation from pre-order sequence.
# 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
You can’t perform that action at this time.