For this Binary Search Tree method. I don't understand how it puts it in order from smallest to-CodePudding

So I understand that it calls the method recursively. However I'm not sure how it would output the larger nodes (the right side of the nodes). Thank you!

void InOrderSmallestToLargest(BST* root)
  {
    if(root==NULL)
    {
      return;
    }

    // Ordered from smallest to largest
    InOrderSmallestToLargest (root->left);
    cout << root->data<<'\n';
    InOrderSmallestToLargest (root->right);
  }

CodePudding user response：

The code you have posted describes a tree-traversal scheme called pre-order (see https://en.wikipedia.org/wiki/Tree_traversal#Pre-order,_NLR )

The cout will print the current nodes value after traversing all the left Nodes (until a leafe is reched) and the continue the traversal on the right Nodes, and then print their values

CodePudding user response：

In a Binary Search Tree (BST) this rule is true for all nodes:

All values in the node's left subtree (if any) are less than or equal to the node's own value
All values in the node's right subtree (if any) are greater than or equal to the node's own value

The recursive function uses this property. The reasoning is that in order to output the values in order, all the values in the root's left subtree should be listed before its own value, and all the values from the root's right subtree should be listed after its own value.

If we apply the same reasoning in the left subtree and in the right subtree, then it is clear we will never output values in the wrong order.