How can I call my functions to calculate preorder of the BST?

Question

I implemented functions in Python to create a binary Search tree. It currently displays the nodes inorder and now I'm trying to get it to display in preorder.

I created the inorder function based on my notes, but I can't figure out how to get preorder to work correctly. Right now it displays the left-most nodes, but I can't get it to backtrack to the right nodes. I'll post my code with sample values. Any tips to get me on the right track would be greatly appreciated. Thanks!

I put all of my code and just the Preorder function code.

---

Full Python Code:

####
#
# Binary Search Tree
#
########

class Node:
    #constructor
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data

    def insert(self,data):
        if(data < self.data):
            if(self.left is None):
                self.left = Node(data)
            else:
                self.left.insert(data)
        elif(data > self.data):
            if(self.right is None):
                self.right = Node(data)
            else:
                self.right.insert(data)


    #lookup node containing data
    #data to lookup and parent nodes parent
    #returns node and its parent if found, otherwise none
    def lookup(self,data,parent=None):
        if(data < self.data):
            if(self.left is None):
                return None, None
            return self.left.lookup(data,self)
        elif(data > self.data):
            if(self.right is None):
                return None, None
            return self.right.lookup(data,self)
        else:
            return self,parent


    #return the number of children (either 0,1,or 2)
    def childrenCount(self):
        children = 0
        if(self.left):
            children += 1
        if(self.right):
            children += 1
        return children

    #delete the node containing data
    #data node content to be deleted
    def delete(self,data):
        node, parent = self.lookup(data)
        if(node is not None):
            childrenCount = node.childrenCount()
        if(childrenCount == 0):
            if(parent):
                if(parent.left is node):
                    parent.left = None
                else:
                    parent.right = None
            del node
        elif(childrenCount == 1):
            if(node.left):
                n = node.left
            else:
                n = node.right
            if(parent):
                if(parent.left is node):
                    parent.left = n
                else:
                    parent.right = n
            del node
        else:
            parent = node
            nextNode = node.right
            while(nextNode.left):
                parent = nextNode
                nextNode = nextNode.left
            node.data = nextNode.data
            if(parent.left == nextNode):
                parent.left = nextNode.right
            else:
                parent.right = nextNode.right

    #display the tree via inorder
    def displayInorder(self):
        global dspList2
        if(self.left):
            self.left.displayInorder()
        dspList2.append(self.data)
        if(self.right):
            self.right.displayInorder()

    def preOrder(self):
        global dspList
#        dspList.append(self.data)
        if(self.left):
            print("Left.. appending",self.data)
            dspList.append(self.data)
            self.left.preOrder()
        if (self.right is None):
            print("No right.. append",self.data)
            dspList.append(self.data)
            

        

dspList = []
dspList2 = []
def main():
    global dspList2
    global dspList
    root = Node(8)
    root.insert(3)
    root.insert(10)
    root.insert(1)
    root.insert(6)
    root.insert(4)
    root.insert(7)
    root.insert(14)
    root.insert(13)
    node,parent = root.lookup(6)


    root.preOrder()
    root.displayInorder()
    print("Inorder:",dspList2)
    print("Preorder:",dspList)

main()

---

Preorder function:

    def preOrder(self):
        global dspList
#        dspList.append(self.data)
        if(self.left):
            print("Left.. appending",self.data)
            dspList.append(self.data)
            self.left.preOrder()
        if (self.right is None):
            print("No right.. append",self.data)
            dspList.append(self.data)
            

Answer 1

Look at the explanations of the traversals on Wikipedia. Your solution is pretty simple, and is a clear translation of the explanation into code. Pre-order is only different from in-order in the order in which it recurses through the tree. Aside from that it's just as simple and straightforward. The required change to your code to get pre-order to work should likewise be a simple change from in-order to pre-order. The code below should work:

def inOrder(self):
    global dspList2
    if(self.left):
        self.left.inOrder()
    dspList2.append(self.data)
    if(self.right):
        self.right.inOrder()

def preOrder(self):
    global dspList
    dspList.append(self.data)
    if(self.left):
        self.left.preOrder()
    if (self.right):
        self.right.preOrder()

Note, rather than using globals, it would be safer and better style to delegate to a helper method that takes an accumulator:

def inOrder(self):
    acc = []
    self.inOrderAcc(self, acc)
    return acc

def inOrderAcc(self, acc):
    if (self.left):
        self.left.inOrderAcc(acc)
    acc.append(self.data)
    if (self.right):
        self.right.inOrderAcc(acc)