Binary Tree Traversals and call stack during that time?

[polaryeti]

       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?

[kirupa]

What you are doing seems to be the equivalent of a depth-first search:

Depth-First Search (DFS) and Breadth-First Search (BFS)

One change to call out is that your stack will only contain the node you are about to explore. It won’t contain a preview of future stacks or include null values.

[hungryfox092]

thanks for sharing..!

[HARRYJOSAN]

Your step-by-step breakdown of the preorder traversal and call stack is excellent! You’re correctly visualizing how each function call is pushed onto the stack, and how left children are processed before right children. After processing 57, since its left and right children are NULL, the stack will pop back to 60, and then preorder root->right for node 100 continues. Your understanding is solid; just remember the stack always mirrors the function call hierarchy.