# How to find the n-th node of the Inorder Traversal of a Binary Tree in C++

In this tutorial, we will learn how to find the n-th node of the inorder traversal of a Binary Tree in C++.

First, we will quickly recap what inorder traversal of a Binary Tree is.

Then we shall look at how displaying the n-th node of the traversal is different from traversing the entire tree.

Finally, we look at the C++ code to implement this.

## Inorder traversal of a Binary Tree in C++

Examples of Linear data structures include stacks and queues. Such data structures are usually traversed in one direction. A Binary Tree is a well-known example of a non-linear data structure. Every element in a Binary Tree is also referred to as a node. A node in a Binary tree contains some data. Apart from this it also points to at most 2 nodes (called children). They are known as the left child and right child respectively. The following image shows a Binary Tree and we will refer to this example throughout this tutorial.

The 2 most common approaches to traversing a tree are Breadth-First Searching (BFS) and Depth First Searching (DFS).

Inorder traversal is a DFS approach. The algorithm for Inorder traversal is as follows.

- Traverse the left sub-tree.
- Access the data of the current node.
- Traverse the right sub-tree.

If we display the data in the nodes of the Binary Tree shown in the above image we get

This article has more on Binary Tree Traversals in C++.

## Finding the n-th node

In the usual Inorder traversal of a Binary Tree, the entire tree is accessed. That is, we go through all the nodes of the tree. Our problem in this tutorial is to display the n-th node of a given Binary Tree.

Consider the Binary Tree shown above. If, say, n is 4, we are required to output only ’12’.

There are 2 simple ways to implement this both having the same idea.

- Use a static counter variable within the ‘n-th node function’.
- Use a global counter variable.

We shall look at the method with the static counter variable in this tutorial.

### Algorithm

Within the function ‘nth_in_order’ that takes a node address and ‘n’ as parameters,

- Initialize static variable ‘ct’ to 0.
- Perform Inorder traversal with ‘ct’ incremented at every node.
- If ‘ct’ is equal to ‘n’, display the data in the node and return to the calling function.

#### Code: find the n-th node of the Inorder Traversal of a Binary Tree in C++

#include <iostream> #include <vector> using namespace std; struct node //We create a node structure having //1 integer datatype and 2 children { int data; node* left; node* right; }; node* new_node(int d) // Function to ensure proper // creation of new nodes in main() { node* n; do { n = (node*)malloc(sizeof(node)); } while (n == NULL); // The do-while loop ensures // that n is created properly n->data = d; n->left = NULL; n->right = NULL; return n; } void nth_in_order(node* ptr, int n) // This function prints the n-th node // in the inorder traversal of // the created Binary Tree { static int ct = 0; if (ptr == NULL) return; if (ct <= n) { nth_in_order(ptr->left, n); ct++; if (ct == n) { cout << ptr->data << " "; return; } nth_in_order(ptr->right, n); } } int main() { node* root = new_node(81); root->left = new_node(42); root->left->left = new_node(8); root->left->left->left = new_node(1); root->left->right = new_node(12); root->left->right->right = new_node(2); root->right = new_node(3); root->right->left = new_node(90); root->right->right = new_node(4); // I have created the same // Binary tree as givenĀ inĀ the // examples in the tutorial int n; cin >> n; nth_in_order(root, n); return 0; }

Example Input

4

Example Output

12

#### Conclusion

In this tutorial, we have seen how to display the n-th node in the inorder traversal of a Binary Tree using C++.

Note: We have assumed that the user enters a valid value for ‘n’.

You can also learn about a more efficient traversal here.

Morris Inorder Tree Traversal in C++

## Leave a Reply

You must be logged in to post a comment.