CODEWITHSUNDEEP
pythonoopdata-structures
Emin Mammadov
Emin Mammadov

Reputation: 155

Append (self) with stacks in Python classes

I am doing/learning data structures and algorithms and I came across the following code:

class BinaryTree:

    def __init__(self, root_data):
        self.data = root_data
        self.left_child = None
        self.right_child = None

    def inorder_iterative(self):
        inorder_list = []
        return inorder_list

    def get_right_child(self):
        return self.right_child

    def get_left_child(self):
        return self.left_child

    def set_root_val(self, obj):
        self.data = obj

    def get_root_val(self):
        return self.data

    def preorder_iterative(self):
        pre_ordered_list = [] #use this as result
        stack = []
        stack.append(self)

        while len(stack)>0:
            node = stack.pop() #should return a value 
            pre_ordered_list.append(node.get_root_val())
            if node.right_child:
                stack.append(node.get_right_child())
            if node.left_child:
                stack.append(node.get_left_child())
        return pre_ordered_list


    bn = BinaryTree(1)
    bn.left_child = BinaryTree(2)
    bn.right_child = BinaryTree(3)
    print (bn.preorder_iterative())

I am very lost about stack.append(self) part. I am not sure what is the point of having this line and I don't fully understand the concept of .append(self). I have learnt that self represents the instance of the class.

Upvotes: 0

Views: 443

Answers (1)

chepner
chepner

Reputation: 531315

The purpose of the stack is to simulate recursion.

The initial value placed on the stack is the tree itself (in the form of its root node). Its value is retrieved, and then each subtree is placed on the stack. On the next iteration of the loop, the left child is removed, processed, and replaced with its children, if any. The loop continues as long as there is anything on the stack to process. Once everything on the left side of the tree as been processed, you'll finally start on the right child (placed the stack way at the beginning of the loop).

Compare to a recursive version:

def preorder_recursive(self):
    result = [self.get_root_val()]
    if node.left_child:
        result.extend(node.left_child.preorder_recursive())
    if node.right_child:
        result.extend(node.right_child.preorder_recursive())
    return result

Each recursive call essentially puts self on a stack, allowing the left child (and its descendants) to be processed before eventually returning to the root and moving to its right child.

Upvotes: 1

Related Questions