Binary Tree: Understanding How In-Order Traversal Works

Tree traversals are a fundamental concept in computer science and are used to visit all the nodes of a tree in a specific order. In this post, we'll discuss how to implement an inorder traversal using a recursive function in TypeScript, and we'll walk through an example to see how the function calls are added to the call stack and how the root node values are returned.

A way of visiting binary tree nodes

An in-order traversal is a way of visiting the nodes of a binary tree in a specific order. The order is defined as follows:

1. Visit the left subtree
2. Visit the root node
3. Visit the right subtree

This order ensures that the nodes are visited in a left-to-right fashion, which can be useful in certain scenarios, such as printing out the values of a binary search tree in ascending order.

In-order traversal in TypeScript

In order to implement an in-order traversal, we can use a recursive function that follows the steps described above. Here is an example of how we could implement an in-order traversal in TypeScript:

function inorderTraversal(root: Node | null): void {
  if (root === null) return; // base case

  inorderTraversal(root.left); // visit left subtree
  console.log(root.val); // visit root node
  inorderTraversal(root.right); // visit right subtree
}

This function takes a binary tree as an input (the "root" node), and it performs an inorder traversal on that tree. It follows the steps described above: it visits the left subtree, then the root node, and then the right subtree.

Recursive function calls added to the call stack

As the function calls itself recursively, it adds new function calls to the top of the call stack. This creates a stack-like structure, with the most recent function call at the top. Let's see how this looks in practice by considering the following example tree:

    F
   / \
  B   G
 / \   \
A   D   I
   /
  C
 /
E

1. The inorderTraversal function is called on the root node (F).
2. The function makes a recursive call on the left subtree of the root node (B).
3. The function makes a recursive call on the left subtree of the left child (A).
4. The function returns and prints the value of the left child (A).
5. The function makes a recursive call on the right subtree of the left child (D).
6. The function makes a recursive call on the left subtree of the right child (C).
7. The function makes a recursive call on the left subtree of the left grandchild (E).
8. The function returns and prints the value of the left grandchild (E).
9. The function returns and prints the value of the right grandchild (C).
10. The function returns and prints the value of the right child (D).
11. The function returns and prints the value of the left child (B).
12. The function makes a recursive call on the right subtree of the root node (G).
13. The function makes a recursive call on the right subtree of the right child (I).
14. The function returns and prints the value of the right grandchild (I).
15. The function returns and prints the value of the right child (G).
16. The function returns and prints the value of the root node (F).

Returning the root node values

As you can see, the function calls are being added to the top of the call stack, and the root node values are being printed as the function returns from each recursive call. The node values are visited in the order A, E, C, D, B, I, G, F, which is the in-order traversal of the tree.

I hope this helps you understand how an in-order traversal works and how the function calls are added to the call stack. An in-order traversal can be a useful way to visit the nodes of a binary tree in a specific order, and it can be implemented using a simple recursive function.

It's worth noting that there are other ways to traverse a binary tree, such as pre-order traversal and post-order traversal. Pre-order traversal visits the root node first, then the left subtree, and then the right subtree. Post-order traversal visits the left subtree first, then the right subtree, and then the root node.

If you have any questions, please let me know in the comments section!