60
/ \
55 100
/ \ / \
45 57 67 107
\ /
59 101
The binary tree to be traversed is as provided above.
The pre-order traversal pseudocode is as presented below:
if(root==NULL) return;
print(root->data);
preorder(root->left);
preorder(root->right);
During the preorder traversal of this binary search tree, I wanted to know how the call stack works.
Initially, root is 60. As soon as the root arrives, it gets printed as per the pre-order traversal algorithm. So root and its left and right children are pushed onto the stack.
+------+-----------+------------+
| root | root->left| root->right|
+------+-----------+------------+
| 60 | 55 | 100 |
+------+-----------+------------+
Then, preorder(55) is called. Immediately 55 gets printed and 55,45,57 gets pushed onto the stack(I mean values are recorded somewhere, for simplicity I assume it is stack).
+------+-----------+------------+
| root | root->left| root->right|
+------+-----------+------------+
| 55 | 45 | 57 |
| 60 | 55 | 100 |
+------+-----------+------------+
Then preorder(45) is called. Immediately 45 gets printed and 45,NULL,NULL is pushed onto the stack.
+------+-----------+------------+
| root | root->left| root->right|
+------+-----------+------------+
| 45 | NULL | NULL |
| 55 | 45 | 57 |
| 60 | 55 | 100 |
+------+-----------+------------+
Since root->left=NULL, top of the stack must be popped and function call returns to preorder(root->right) i.e. root=57 onwards
57 is pushed onto the stack with two NULL values and immediately been printed.
+------+-----------+------------+
| root | root->left| root->right|
+------+-----------+------------+
| 57 | NULL | NULL |
| 55 | 45 | 57 |
| 60 | 55 | 100 |
+------+-----------+------------+
Now what should happen? And could you correct me if I was wrong?
