"""
Created by Hadron DaVinci
https://hadrondavinci.com

For Educational Purposes
To Run:
    1) Download https://hadrondavinci.com/assets/code/2020-11-01/method1.py
    2) python method1.py

Expected Output:
The Preordering of tree is: [6, 3, 2, '~', '~', 5, 7, '~', '~', 4, '~', '~', 5, '~', 4, '~', '~']
The Inordering of tree is: ['~', 2, '~', 3, '~', 7, '~', 5, '~', 4, '~', 6, '~', 5, '~', 4, '~']
The Postordering of tree is: ['~', '~', 2, '~', '~', 7, '~', '~', 4, 5, 3, '~', '~', '~', 4, 5, 6]
"""


class BinaryTreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


class BinaryTree:
    def __init__(self, node_list: list, null_char="~"):
        """
        Since root node is at the end of the input node_list,
        The list is reversed so this code still starts at the root node
        :param node_list: input of node information
        :param null_char: represents end of path
        """
        self.null_char = null_char
        self.node_list = node_list[::-1]
        self.build_index = 0
        self.root = self.insert_next_node()

    def insert_next_node(self):
        """
        Builds tree with postorder input by appending the next node.
        Since the input was reversed, code passes by right node before left node.
        :return: temp_node
        """
        temp_node = None
        data = self.node_list[self.build_index]
        if data != self.null_char:
            temp_node = BinaryTreeNode(data=data)
        self.build_index += 1

        if temp_node:
            temp_node.right = self.insert_next_node()
            temp_node.left = self.insert_next_node()
        return temp_node

    def get_ordering(self, node, order_type):
        """
        Walks binary entire binary tree in a particular order.
        Generates nodes along the way.
        :param node: node to start walking
        :param order_type: type of order used
        :return:
        """
        if node is None:
            yield None
            return

        if order_type == "pre": yield node
        yield from self.get_ordering(node.left, order_type)
        if order_type == "in": yield node
        yield from self.get_ordering(node.right, order_type)
        if order_type == "post": yield node

    def create_node_list(self, order_type='pre'):
        node_list = []
        for node in self.get_ordering(self.root, order_type):
            if node is None:
                node_list.append(self.null_char)
                continue
            node_list.append(node.data)

        return node_list


if __name__ == "__main__":
    postorder_node_data = ['~', '~', 2, '~', '~', 7, '~', '~', 4, 5, 3, '~', '~', '~', 4, 5, 6]
    bt = BinaryTree(postorder_node_data)
    print('The Preordering of tree is:', bt.create_node_list('pre'))
    print('The Inordering of tree is:', bt.create_node_list('in'))
    print('The Postordering of tree is:', bt.create_node_list('post'))