Iterative Inorder Traversal

Problem

Return the inorder traversal of a binary search tree built from the given values, using an explicit stack instead of recursion.

Insert the values in order (duplicates ignored). The iterative algorithm walks left pushing nodes, pops to visit, then moves to the right child.

Return the sorted list of values.

Hint

Push nodes while going left; pop, visit, then continue into the right child.

case 1

in: [[5,3,8,1]]

expected: [1,3,5,8]

case 2

in: [[]]

expected: []

case 3

in: [[2,1]]

expected: [1,2]

case 4

in: [[4,2,6,1,3,5,7]]

expected: [1,2,3,4,5,6,7]

Starter codePython

def inorder_traversal(values):
    # Your code here
    pass

4 test cases · run your code against them in the editor