Tree

• 173. Binary Search Tree Iterator （Medium)

Pre-order: middle->left->right

F, B, A, D, C, E, G, I, H. Check if the current node is empty / null Display the data part of the root (or current node). Traverse the left subtree by recursively calling the pre-order function. Traverse the right subtree by recursively calling the pre-order function. In-order

In-order: left->middle->right

A, B, C, D, E, F, G, H, I. Check if the current node is empty / null Traverse the left subtree by recursively calling the in-order function. Display the data part of the root (or current node). Traverse the right subtree by recursively calling the in-order function. In a search tree, in-order traversal retrieves data in sorted order.[4]

Post-order: left->right->middle

A, C, E, D, B, H, I, G, F. Check if the current node is empty / null Traverse the left subtree by recursively calling the post-order function. Traverse the right subtree by recursively calling the post-order function. Display the data part of the root (or current node).

The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited root.

No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely.