C Program to Find Nth Node of Inorder Traversal

This C Program finds nth node in the inorder traversal of a tree.

Here is source code of the C Program to find nth node in the inorder traversal of a tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Find Nth Node in the Inorder Traversal of a Tree
  3.  */
  4.  
  5. typedef struct node
  6. {
  7.     int value;
  8.     struct node *left;
  9.     struct node *right;
  10. }newnode;
  11.  
  12. newnode *root;
  13. static ctr;
  14.  
  15. void nthnode(newnode *root, int n, newnode **nthnode);
  16. int main()
  17. {
  18.     newnode *temp;
  19.     root=0;
  20.  
  21.     // Construct the tree
  22.     add(19);
  23.     add(20);
  24.     add(11);
  25.     inorder(root);
  26.     // Get the pointer to the nth Inorder node
  27.     nthinorder(root, 6, &temp);
  28.     printf("\n[%d]\n", temp->value);
  29.     return(0);
  30. }
  31.  
  32. // Get the pointer to the nth inorder node in "nthnode"
  33. void nthinorder(newnode *root, int n, newnode **nthnode)
  34. {
  35.     static whichnode;
  36.     static found;
  37.  
  38.     if (!found)
  39.     {
  40.         if (root)
  41.         {
  42.             nthinorder(root->left, n , nthnode);
  43.             if (++whichnode == n)
  44.             {
  45.                 printf("\n Found %dth node\n", n);
  46.                 found = 1;
  47.                 *nthnode = root;
  48.             }
  49.             nthinorder(root->right, n , nthnode);
  50.         }
  51.     }
  52. }
  53.  
  54. inorder(newnode *root)
  55. {
  56. }
  57. // Add value to a Binary Search Tree
  58. add(int value)
  59. {
  60.     newnode *temp, *prev, *cur;
  61.  
  62.     temp = malloc(sizeof(newnode));
  63.     temp->value = value;
  64.     temp->left  = 0;
  65.     temp->right = 0;
  66.     if (root == 0)
  67.     {
  68.         root = temp;
  69.     }
  70.     else
  71.     {
  72.         prev = 0;
  73.         cur = root;
  74.         while(cur)
  75.         {
  76.             prev = cur;
  77.             cur =(value < cur->value)? cur->left : cur->right;
  78.         }
  79.         if (value > prev->value)
  80.             prev->right = temp;
  81.         else
  82.             prev->left  = temp;
  83.     }
  84. }

$ cc pgm63.c
$ a.out
 
[1416572]

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at other example programs on Trees, go to Trees. If you wish to look at programming examples on all topics, go to C Programming Examples.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.