prawn-cake / data_structures Goto Github PK

    @classmethod
    def pre_order_traversal(cls, node):
        order = []
        stack = [node]
        while stack:
            current_node = stack.pop()
            order.append(current_node.value)
            if current_node.right:
                stack.append(current_node.right)

            # Put left always on top of stack
            if current_node.left:
                stack.append(current_node.left)

        return order
...
    @classmethod
    def level_order_traversal(cls, node):
        """Level order traversal is implemented with queue
        Steps:
            1. Add node value to order list and go ahead
            2. Put next node to the queue (left AND/OR right if exists)
            3. Declare while loop and repeat first two steps until the length
            is 0
        """
        order = []
        queue = deque([node])

        while len(queue) != 0:
            current_node = queue.pop()
            order.append(current_node.value)
            if current_node.left:
                queue.appendleft(current_node.left)
            if node.right:
                queue.appendleft(current_node.right)

        return order

@classmethod
    def in_order_traversal(cls, node):
        order = []
        stack = []

        current_node = node
        while stack or current_node is not None:
           # go down till the last left child
            if current_node is not None:
                stack.append(current_node)
                current_node = current_node.left
            else:
                # once we reach last left child start to visit closest right child
                current_node = stack.pop()
                order.append(current_node)
                current_node = current_node.right
        return order
...
etc