C++ Data Structures and Algorithms

Traversing a BST in order

We have successfully created a new BST and can insert a new key into it. Now, we need to implement the PrintTreeInOrder() operation, which will traverse the BST in order from the smallest key to the greatest key. To achieve this, we will go to the leftmost node and then to the rightmost node. The code should be as follows:

void BST::PrintTreeInOrder(BSTNode * node){    // Stop printing if no node found    if(node == NULL)        return;    // Get the smallest key first    // which is in the left subtree    PrintTreeInOrder(node->Left);    // Print the key    std::cout << node->Key << " ";    // Continue to the greatest key    // which is in the right subtree    PrintTreeInOrder(node->Right);}

Since we will always traverse from the root node, we can ...