CODEWITHSUNDEEP
pythonglobal-variablestree-traversal
Taylor Shmaylor
Taylor Shmaylor

Reputation: 11

Return a list of tree nodes in the correct order using a recursive in/pre/post order method without using a global variable

I am currently trying to get the correct sorting of nodes for a binary tree when traversed with in/pre/post order using recursive methods. The only solution I've been able to get to work involves a global variable to hold the list for each type of traversal. I would like to find a way to get the results I am getting without using a global variable for the sorted lists.

Here is my code:

class Node: 
    def __init__(self,key,left,right): 
        self.left = left
        self.right = right
        self.val = key 

#GLOBAL VARIABLES
inList = []
preList = []
postList = []

#NO GLOBAL VARIABLE USED HERE
def inorder(root): 
    if root: 
        inorder(root.left) 
        print(root.val), 
        inorder(root.right) 

def postorder(root): 
    if root: 
        postorder(root.left) 
        postorder(root.right) 
        postList.append(root.val) 

    return postList

def preorder(root):
    if root: 
        preList.append(root.val) 
        preorder(root.left)  
        preorder(root.right)

    return preList

def testCase(testNumber, function, root, expectedAnswer):
    if expectedAnswer==function(root):
        print "Test", testNumber, "passed."
    else:
        print "Test", testNumber, "failed."

def test1():
    f = Node("f", [], [])
    c = Node("c", f, [])
    e = Node("e", [], [])
    g = Node("g", [], [])
    d = Node("d", [], g)
    b = Node("b", d, e)

    root = Node("a", b, c)

    testCase(1, inorder, root, ['d', 'g', 'b', 'e', 'a', 'f', 'c'])
    testCase(2, preorder, root, ['a', 'b', 'd', 'g', 'e', 'c', 'f'])
    testCase(3, postorder, root, ['g', 'd', 'e', 'b', 'f', 'c', 'a'])
    testCase(4, inorder, c, ['f','c'])
    testCase(5, preorder, e, ['e'])

Upvotes: 0

Views: 1475

Answers (2)

Kevin He
Kevin He

Reputation: 1250

You can use inorder traversal and return the sorted list of the current subtree, and join them recursively like this left_subtree_result + [current_node] + right_subtree_result. In this case a linkedlist would give better performance since join is O(1). (By join I mean concatenation)

The code would be 

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node] + inorder(node.right)

Upvotes: 1

Mad Physicist
Mad Physicist

Reputation: 114230

Just pass the list to fill in to your function. You don't even need to return it since appending modifies the list in-place. Since your three traversals are nearly identical, I will focus on inorder:

Add an extra argument:

def inorder(root, inList):
    if root: 
        inorder(root.left, inList) 
        inList.append(root.val)
        inorder(root.right, inList)

Once you have done this for all three methods (including removing the return statements), you can update your testCase function to pass in a local list:

def testCase(testNumber, function, root, expectedAnswer):
  actualAnswer = []
  function(root, actualAnswer)

  if expectedAnswer == actualAnswer:
      print "Test", testNumber, "passed."
  else:
      print "Test", testNumber, "failed."

Upvotes: 0

Related Questions