This lesson's interactive features are locked, please to keep using them

Inorder Traversal

An "inorder" traversal is the most intuitive way to visit all the nodes in a tree. It's called "inorder" because the current node is visited between its children. It results in an ordered list of the nodes in the tree. The following tree:

Would be visited in this order:

[2, 3, 5, 7, 8, 9, 10, 12]

Assignment

Turns out, the data team had no idea what they were talking about, and our product lead just wanted an export of our tree in sorted order. He wants to be able to see the users in the order they signed up (and were thus given user IDs).

Implement the recursive inorder method. Here are the algorithm's steps:

Recursively traverse the left subtree
Visit the value of the current node by appending its value to the visited array
Recursively traverse the right subtree
Return the list of nodes visited so far