BST Traversal

The solution implements three different depth-first traversal methods for binary trees: in-order traversal, pre-order traversal, and post-order traversal.

These traversal methods visit each node in the tree in a specific order, allowing for different ways to process or search through the tree.

# O(n) time | O(n) space
def in_order_traverse(tree, array):
	if tree is not None:
		in_order_traverse(tree.left, array)
		array.append(tree.value)
		in_order_traverse(tree.right, array)
	return array
# O(n) time | O(n) space	
def pre_order_traverse(tree, array):
	if tree is not None:
		array.append(tree.value)
		pre_order_traverse(tree.left, array)
		pre_order_traverse(tree.right, array)
	return array

# O(n) time | O(n) space	
def post_order_traverse(tree, array):
	if tree is not None:
		post_order_traverse(tree.left, array)
		post_order_traverse(tree.right, array)
		array.append(tree.value)
	return array

In-order Traversal

In in-order traversal, the nodes are visited in the order: left subtree, current node, right subtree. This traversal method is commonly used for binary search trees (BSTs) to visit nodes in non-decreasing order.

Pre-order Traversal

In pre-order traversal, the nodes are visited in the order: current node, left subtree, right subtree. This traversal method is often used for creating a copy of the tree or evaluating expressions.

Post-order Traversal

In post-order traversal, the nodes are visited in the order: left subtree, right subtree, and current node. This traversal method is often used for deleting nodes from a tree or evaluating expressions.

In each of the cases above, the respective functions recursively traverses the tree in in-order, pre-order, and post-order fashion and appends the values of the nodes to the array parameter.

Time & Space Complexities

Each of these traversal methods has a time complexity of O(n) and a space complexity of O(n), where n is the number of nodes in the tree.

This is because each node in the tree is visited once, and the space required for the traversal is proportional to the height of the tree, which can be at most O(n) for unbalanced trees.

Unit Tests
 

The unit tests below cover various scenarios to ensure the robustness of the tree traversal solution. some of these include:~

•     Traversal of an empty tree.
•     Traversal of a single-node tree.
•     Traversal of a balanced tree.
•     Traversal of an unbalanced tree.
•     Traversal of a tree with duplicate values.
•     Traversal of a large tree.

import unittest


class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


class TestTreeTraversal(unittest.TestCase):
    def test_in_order_traverse(self):
        # Construct a binary tree
        #        1
        #       / \
        #      2   3
        #     / \
        #    4   5
        root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        root.left.left = TreeNode(4)
        root.left.right = TreeNode(5)

        # Expected in-order traversal: [4, 2, 5, 1, 3]
        self.assertEqual(in_order_traverse(root, []), [4, 2, 5, 1, 3])

    def test_pre_order_traverse(self):
        # Construct a binary tree
        #        1
        #       / \
        #      2   3
        #     / \
        #    4   5
        root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        root.left.left = TreeNode(4)
        root.left.right = TreeNode(5)

        # Expected pre-order traversal: [1, 2, 4, 5, 3]
        self.assertEqual(pre_order_traverse(root, []), [1, 2, 4, 5, 3])

    def test_post_order_traverse(self):
        # Construct a binary tree
        #        1
        #       / \
        #      2   3
        #     / \
        #    4   5
        root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        root.left.left = TreeNode(4)
        root.left.right = TreeNode(5)

        # Expected post-order traversal: [4, 5, 2, 3, 1]
        self.assertEqual(post_order_traverse(root, []), [4, 5, 2, 3, 1])

    def test_empty_tree(self):
        # Traversal of an empty tree should return an empty list
        self.assertEqual(in_order_traverse(None, []), [])
        self.assertEqual(pre_order_traverse(None, []), [])
        self.assertEqual(post_order_traverse(None, []), [])

    def test_single_node_tree(self):
        # Traversal of a single-node tree
        root = TreeNode(1)
        self.assertEqual(in_order_traverse(root, []), [1])
        self.assertEqual(pre_order_traverse(root, []), [1])
        self.assertEqual(post_order_traverse(root, []), [1])

    # Add more test cases to cover other scenarios...


if __name__ == '__main__':	
    unittest.main()