|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
treeNode * insert(treeNode * node, int data) { if(node==NULL) { return new treeNode(data, NULL, NULL); } if ( data > node->data ) { node->right = insert( node->right, data ); } else if ( data <= node->data ) { node->left = insert( node->left, data ); } return node; } |
First we are given the tree at node 5
1) We push function insert onto the stack with the parameter of a node with data 5.
2) We check to see if the node with data 5 is NULL or not. It is not, so we move on.
3) the data we want to insert is less than 5
4) thus we go down the left side of the tree because the data we want to insert, 2, is less than the current node’s data of 5. We travel left down the node tree by pushing another insert function with the parameter of the left side of our node, which is node->left.
The call^r means we call the insert function recursively. The insert function returns the node that it represents, which is also a node tree. Hence we need to point our node->left to whatever node tree the recursion function returns.
5) node->left evaluates to node with data 1. Hence, we push function insert onto the stack with the parameter of a node with data 1.
1) Once function insert with node data 1 gets pushed onto the stack, we then evaluate to see if that node is NULL. Obviously, it is not.
2) The data we want to insert, 2, is bigger than current node data of 1.
3) Thus, we want to travel towards right. We go down the right side of the tree by pushing another insert function with the parameter of the right side of our current node, which is node->right.
The call^r means we call the insert function recursively. The insert function returns the node that it represents, which is also a node tree. Hence we need to point our node->right to whatever node tree the recursion function returns.
We need to assign node->right to whatever node tree the recursion function returns.
4) node->right evaluates to NULL. We push function insert with parameter NULL onto the stack.
5) We see that the parameter is NULL, which means we reached to the end and is ready to place our insertion data 2 here. We create a new node of data 2.
6) We return this newly created node.
1) Then we pop the insert function with parameter NULL.
2) We now continue where we left off from insert function with parameter node of data 1. We had its right point to whatever the recursive insert returns. The recursive insert function returned newly created node of data 2. Thus, we assign the parameter node of data 1’s right to the newly created node of data 2.
3) We then continue execution and return the current node of data 1.
4) We pop insert function with node of data 1.
1) We now continue where we left off at insert function with parameter node of data 5. We had our left point to whatever the recursive insert returns. The recursive insert function returned node of data 1’s address and we have our current node 5’s left point to it.
2) Then we reach the end of the function definition by returning the current node with data 5.
3) Finally the original insert function starting with node of data 5 gets popped off the call stack.