Depth-First Search for binary tree. In-order traversal

dfs-inorder.py

"""
Depth-First Search for binary tree
In-order traversal
"""

import unittest

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

def inOrder(root):
    result = []
    stack = []
    res = [] # list with nodes data

    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        
        else:
            node = stack.pop()
            result.append(node)
            root = node.right

    for i in result:
        res.append(i.data)
    return res


class TestMethods(unittest.TestCase):

    def test_inOrder(self):
        self.assertEqual(inOrder(root), [2, 3, 4, 5, 6, 7, 8, 9])

    def test_empty_inOrder(self):
        self.assertEqual(inOrder(None), [])

    def test_single_item_bfs(self):
        self.assertEqual(inOrder(root1), [500])    



n2 = Node(2)
n3 = Node(3, n2)
n5 = Node(5)
n4 = Node(4, n3, n5)
n7 = Node(7)
n9 = Node(9)
n8 = Node(8, n7, n9)
root = Node(6, n4, n8)

# another tree
root1 = Node(500)

print inOrder(root) 


unittest.main()