# Binary search tree traversal and depth first search in Python

I am learning about the tree traversal, and I would like to ask for feedback.

Using recursion, write a function that takes in a binary search tree and number of outputs a list of values ordered by depth first traversal, pre-order, in-order, post-order.

#    PRE-ORDER
#
#      Input: node {TreeNode}
#      Output: {List}
#
#

def dfs_pre(node):
result = []
def traverse(node):
nonlocal result
if node is None: return
result.append(node.value)
traverse(node.left)
traverse(node.right)

traverse(node)
return result

#
#  Using recursion, write a function that takes in a binary search tree and
#      outputs a list of values ordered by IN-ORDER DEPTH FIRST traversal.
#
#      Input: node {TreeNode}
#      Output: {List}
#
#

def dfs_in(node):
result = []
def traverse(node):
nonlocal result
if node is None: return
traverse(node.left)
result.append(node.value)
traverse(node.right)

traverse(node)
return result

#
#   Using recursion, write a function that takes in a binary search tree and
#      outputs a list of values ordered by POST-ORDER DEPTH FIRST traversal.
#
#      Input: Binary Search Tree
#      Output: List
#
#

def dfs_post(node):
result = []
def traverse(node):
nonlocal result
if node is None: return
traverse(node.left)
traverse(node.right)
result.append(node.value)

traverse(node)
return result


Here's the basic testing:

from io import StringIO
import sys

class Capturing(list):
def __enter__(self):
self._stdout = sys.stdout
sys.stdout = self._stringio = StringIO()
return self

def __exit__(self, *args):
self.extend(self._stringio.getvalue().splitlines())
sys.stdout = self._stdout

# code for checking if lists are equal
def lists_equal(lst1, lst2):
if len(lst1) != len(lst2):
return False
for i in range(0, len(lst1)):
if lst1[i] != lst2[i]:
return False
return True

# generate test tree for the rest of the tests
test_tree = TreeNode(4)
test_tree.left = TreeNode(2)
test_tree.left.left = TreeNode(1)
test_tree.left.right = TreeNode(3)
test_tree.right = TreeNode(5)
test_tree.right.right = TreeNode(7)
test_tree.right.right.left = TreeNode(6)
test_tree.right.right.right = TreeNode(8)

print('pre-order depth first search tests')
test_count = [0, 0]

def test():
results = dfs_pre(test_tree)
return lists_equal(results, [4, 2, 1, 3, 5, 7, 6, 8])

expect(test_count, 'able to return values of BST in pre-order depth first manner - [4,2,1,3,5,7,6,8]', test)

def test():
results = dfs_pre(deserialize([]))
return lists_equal(results, [])

expect(test_count, 'returns an empty erray for an empty BST', test)

print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')

print('in-order depth first search tests')
test_count = [0, 0]

def test():
results = dfs_in(test_tree)
return lists_equal(results, [1, 2, 3, 4, 5, 6, 7, 8])

expect(test_count, 'able to return values of BST in an in-order depth first manner - [1,2,3,4,5,6,7,8]', test)

def test():
results = dfs_in(deserialize([]))
return lists_equal(results, [])

expect(test_count, 'returns an empty erray for an empty BST', test)

print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')

print('post-order depth first search tests')
test_count = [0, 0]

def test():
results = dfs_post(test_tree)
return lists_equal(results, [1, 3, 2, 6, 8, 7, 5, 4])

expect(test_count, 'able to return values of BST in post-order depth first manner - [1,3,2,6,8,7,5,4]', test)

def test():
results = dfs_post(deserialize([]))
return lists_equal(results, [])

expect(test_count, 'returns an empty erray for an empty BST', test)

print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')


It passed all of the tests.

pre-order depth first search tests
1)    true : able to return values of BST in pre-order depth first manner - [4
,2,1,3,5,7,6,8]
2)    true : returns an empty erray for an empty BST
PASSED: 2 / 2

in-order depth first search tests
1)    true : able to return values of BST in an in-order depth first manner -
[1,2,3,4,5,6,7,8]
2)    true : returns an empty erray for an empty BST
PASSED: 2 / 2

post-order depth first search tests
1)    true : able to return values of BST in post-order depth first manner - [
1,3,2,6,8,7,5,4]
2)    true : returns an empty erray for an empty BST
PASSED: 2 / 2

• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Commented Aug 16, 2018 at 7:25

You should probably replace your # YOUR WORK HERE comments with """docstrings""" describing what the functions do.
Your lists_equal() function could be made shorter, and perhaps a little clearer, by using all(), zip() and list comprehension:
def lists_equal(lst1, lst2):