Binary Search Tree Traversals in C++
So this will pretty much wrap up our short expedition into binary trees. Remember that these functions rely on my earlier posts dealing with the class and nodes.
The three types of traversals we will look at are:
- Preorder (root, left, right)
- Inorder (left, root, right)
- Postorder (left, right, root)
Preorder Traversal
This type of traversal can be used to create duplicates of a tree and can be used to implement prefixes. Whatever order of values you put into a tree will be the order that preorder traversal gives you. So If I enter, 5 7 4 2 1 9 8 3 6 into a binary tree, when I use preorder traversal, I will expect to see 5 7 4 2 1 9 8 3 6.
void preorderTraversal (Node* n) { if (n != nullptr) { //make sure we have a value cout << n->data << endl; //Print out the current Node value preorderTraversal(n->left); //traverse down the left side preorderTraversal(n->right); //Once we return from the left, go down the right } }
Inorder Traversal
This type of traversal will return data sorted in order. So if I entered, 5 7 4 2 1 9 8 3 6, I would expect to see 1 2 3 4 5 6 7 8 9.
void inorderTraversal (Node* n) { if (n != nullptr) { //make sure we have a value inorderTraversal(n->left); //traverse down the left side cout << n->data << endl; //Print out the current Node value inorderTraversal(n->right); //Once we return from the print, go down the right } }
Postorder Traversal
This type of traversal can be used to implement postfixes and can cleanly be used to destroy a tree with out leaving Nodes floating around corrupting memory. So if I entered, 5 7 4 2 1 9 8 3 6, I would expect to see 1 3 2 4 6 8 9 7 5
void postorderTraversal (Node* n) { if (n != nullptr) { //make sure we have a value postorderTraversal(n->left); //traverse down the left side postorderTraversal(n->right); //Once we return from the left, go down the right cout << n->data << endl; //Print out the current Node value } }
For more information on binary trees, I would checkout this article. It goes into detail on how traversals on called on the tree and gives some great visuals. I also liked this interactive visual for binary search trees in general.
Good luck!