Find n-th node of the inorder traversal

Algorithm

Let’s have a look at the step-by-step solution to the problem.

Step 1: Recursively traverse the left subtree.

Step 2: Visit the root node.

Step 3: Recursively traverse the right subtree.

Step 4: In simple Inorder Traversal, we maintain track of how many nodes we've visited so far while traversing and then we print the node when the count reaches n.

Implementation

Let us have a look at the implementation of the above algorithm.

// Code to find the n-th node of the inorder traversal of a Binary Tree. 
#include <stdio.h> 
#include <stdlib.h> 
  
/* A binary tree node */
struct Node { 
    int data; 
    struct Node* left; 
    struct Node* right; 
}; 
  
/*function that allocates a new node */
struct Node* newNode(int data) 
{ 
    struct Node* node = 
          (struct Node*)malloc(sizeof(struct Node)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 
  
    return (node); 
} 
  
/*print its nth nodes of inorder*/
void PrintNthOrder(struct Node* node, int n) 
{ 
    static int cnt = 0; //count tracker
    if (node == NULL) 
        return; 
  
    if (cnt <= n) { 
  
        /* first recur on left child */
        PrintNthOrder(node->left, n); 
        cnt++; 
  
        // when cnt = n then print element 
        if (cnt == n) 
            printf("%d ", node->data); 
  
        /* now recur on right child */
        PrintNthOrder(node->right, n); 
    } 
} 
  
/* Driver program to test above functions*/
int main() 
{ 
    struct Node* root = newNode(33); 
    root->left = newNode(34); 
    root->right = newNode(35); 
    root->left->left = newNode(36); 
    root->left->right = newNode(37); 
    root->right->left = newNode(38); 
  
    int n = 2; 
  
    PrintNthOrder(root, n); 
    return 0; 
} 

You can also try this code with Online C++ Compiler

Run Code

Output: 

34

Algorithm complexities

Let us have a look at the time and space complexity.

Time complexity

O(n), if a tree has n nodes, then each node is visited only once in the inorder traversal.

Space complexity

If we don’t consider the size of the stack for function calls then O(1). Otherwise, O(h) where h is the height of the tree.

Also check out - Inorder Predecessor

Frequently Asked Questions

Can the inorder traversal sequence and the preorder traversal sequence be the same? 

Both the inorder and preorder traversal sequences would be the same if the nodes of the binary tree had only the right children.

What is the best approach for traversing a tree?

Typically, the best optimal algorithm is the one that is tailored to a particular use case and platform. Whether you order in advance, preorder, or after makes no difference. Or whether you're a DFS or BFS player.

What are the uses of trees?

Data with an inherent hierarchical structure can be stored in trees. In its file management system, an operating system may, for example, utilize a tree for directories, files, and folders. They are dynamic, which means that adding and removing nodes is simple.

What are some advantages of using post-order traversal in a binary tree?

It is used to get Reverse Polish Notations.

Conclusion

In this article, we have extensively discussed finding the n-th node of the inorder traversal of a Binary Tree. We started with the introduction of the inorder traversal, the problem statement to find the n-th node of the inorder traversal of a Binary Tree, the example of the problem, the algorithm, and finally concluded with the implementation of the same.

After finding the n-th node of the inorder traversal of a Binary Tree, are you not feeling excited to read/explore more articles on the topic of binary trees? Don't worry; Coding Ninjas has you covered. To learn, see the traversal of the binary tree, Diagonal Traversal of Binary Tree (Recursive and Iterative), and Specific Level Order Traversal of Binary Tree.

Recommended problems -

• Preorder Traversal
• Zig Zag Tree Traversal

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your capacity in coding, you may check out the mock test series and participate in the contests hosted on the Coding Ninjas Studio website. But if you have just started learning and are looking for questions asked by tech giants like Amazon, Microsoft, Google, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

You may also consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!