void IntBinaryTree::insert(TreeNode*& tree, int num) {
  //[1] Base Case: is the node empty?
  if (!tree) {  // if node is empty, create one
    tree = new TreeNode(num);
    return;
  }

  //[2] Does the value already exist in the tree?
  if (tree->value == num)
    return;

  //[3] node passed not empty? If less than head pass left otherwise right
  if (tree->value > num)
    insert(tree->left, num);
  else
    insert(tree->right, num);
}

void IntBinaryTree::displayInOrder(TreeNode* root) {
  if (root) {
    displayInOrder(root->left);
    std::cout << root->value << " ";
    displayInOrder(root->right);
  }
}

I want to understand why the displayInOrder function works? Let's say there's a tree that looks like this:

   5
  / \
 3    7
/ \  / \
1  4 6  8

In order to display this tree in numerical order, you're going to want to read the leftmost values on the left first, then the root, and then the leftmost values on the right, and then the rightmost value last.

Now, the displayinorder function starts of with an if conditional. Simply saying, if the input doesn't equate to false, then keep going left. My question is, once we get to the leftmost value (1, in my example above) wouldn't the next call of "displayInOrder(root->left);" equate to the leftmost value of 1 (Which is NULL by default) and wouldn't NULL make the if conditional false?

How is it that this function seemingly knows to not call the leftmost value of 1?

CodePudding user response：

this is because of the recursion. In the recursive call of displayInOrder(root->left) , the current root pointer is set to point to root->left. But we know that root (for this context it is root->left from the previous call) is pointing to null. So, the if block is not executed and the recursion does backtrack and go to its caller function (when the root was not null and had value of 1). Then it executes the next line of code which prints 1 to the console. Then similar goes on until the recursion terminates. Hope this helps!

CodePudding user response：

It actually calls to display the left child of node(1), but that's NULL or nullptr, we know that if(NULL) is equiv to if(false) and thus the call of displayinorder(node1->left) will not enter the if and straightly return to the caller displayinorder(node1).

// stack of function calls
display(5)
  ->display(3)
    -> display(1)
      -> display(NULL)
      print 1
      -> display(NULL)
    print 3
    -> display(4)
      -> display(NULL)
      print 4
      -> display(NULL)
  print 5
  -> display(7)
// ...