Traversal in BST | Rust

Write three functions that will traverse a Binary Search Tree in Pre-Order, Post-Order, In-Order and return the result array.

In-Order: left child values, parent value, right child values

Pre-Order: parent value, left child values, right child values

Post-Order: left child values, right child values, parent value

We will use recursion to keep track of the parent node as we call the helper method in every node.

The traversing is similar for every Function, but the place where we push the current value to our result array matters.

In inorder we will push the current value after visiting all our left child nodes.

In preorder we will push the current value before visiting any child nodes.

In postorder we will push the current value after visiting all our child nodes.

In-order Traversal

Here we called the push method after visiting all our left child nodes.

Pre-Order Traversal

Here we have called the push method before visiting any of our child nodes.

Post-Order Traversal

Here we have called the push method after visiting all our child node.

Code available here.

Result

Time Complexity is O(n) as we visit every node in the Tree

Space Complexity is O(n) as we store a result array of length n.