Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
2.1.
Example
3.
Algorithm
4.
Implementation
5.
Algorithm complexities
5.1.
Time complexity
5.2.
Space complexity
6.
Frequently Asked Questions
6.1.
Can the inorder traversal sequence and the preorder traversal sequence be the same? 
6.2.
What is the best approach for traversing a tree?
6.3.
What are the uses of trees?
6.4.
What are some advantages of using post-order traversal in a binary tree?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find n-th node of the inorder traversal

Author SAURABH ANAND
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will find the n-th node of the inorder traversal of a Binary Tree. First of all, let’s get started with the introduction to find the n-th node of the inorder traversal of a binary tree.

In an inorder traversal, the left child (including its full subtree) is visited first, followed by the node, and finally the right child (including its entire subtree).

A binary tree

A binary tree

In order traversal of the above binary tree is (Left, Root, Right)  13 12 14 11 15.

Problem statement

We have to find the n-th node of the inorder traversal of a Binary Tree. 

Let us understand the problem statement with the help of some examples.

Example

a) Let’s have a look at this example.

example 1

In order traversal of the above binary tree is (Left, Root, Right) 8, 7, 9, 6, 76, 15 

If n=3 then n-th node of the inorder traversal of a Binary Tree will be 9.

b) Let’s have another example

example 2

In order traversal of the above binary tree is (Left, Root, Right) 8, 7, 9, 6, 76, 15, 98

If n=2 then n-th node of the inorder traversal of a Binary Tree will be 7.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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; 
} 


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 treeDiagonal Traversal of Binary Tree (Recursive and Iterative), and Specific Level Order Traversal of Binary Tree.

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem 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 problemsinterview 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!

thank you

Live masterclass