# Find n-th node in Postorder traversal of a Binary Tree

Hello Everyone,

Given a Binary tree and a number N, write a program to find the N-th node in the Postorder traversal of the given Binary tree.

The idea to solve this problem is to do post-order traversal of the given binary tree and keep track of the count of nodes visited while traversing the tree and print the current node when the count becomes equal to N.

Below is the implementation of the above approach:

`// C++ program to find n-th node of`

`// Postorder Traversal of Binary Tree`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

` `

`// node of tree`

`struct` `Node {`

` ` `int` `data;`

` ` `Node *left, *right;`

`};`

` `

`// function to create a new node`

`struct` `Node* createNode(` `int` `item)`

`{`

` ` `Node* temp = ` `new` `Node;`

` ` `temp->data = item;`

` ` `temp->left = NULL;`

` ` `temp->right = NULL;`

` `

` ` `return` `temp;`

`}`

` `

`// function to find the N-th node in the postorder`

`// traversal of a given binary tree`

`void` `NthPostordernode(` `struct` `Node* root, ` `int` `N)`

`{`

` ` `static` `int` `flag = 0;`

` `

` ` `if` `(root == NULL)`

` ` `return` `;`

` `

` ` `if` `(flag <= N) {`

` `

` ` `// left recursion`

` ` `NthPostordernode(root->left, N);`

` `

` ` `// right recursion`

` ` `NthPostordernode(root->right, N);`

` `

` ` `flag++;`

` `

` ` `// prints the n-th node of preorder traversal`

` ` `if` `(flag == N)`

` ` `cout << root->data;`

` ` `}`

`}`

` `

`// driver code`

`int` `main()`

`{`

` ` `struct` `Node* root = createNode(25);`

` ` `root->left = createNode(20);`

` ` `root->right = createNode(30);`

` ` `root->left->left = createNode(18);`

` ` `root->left->right = createNode(22);`

` ` `root->right->left = createNode(24);`

` ` `root->right->right = createNode(32);`

` `

` ` `int` `N = 6;`

` `

` ` `// prints n-th node found`

` ` `NthPostordernode(root, N);`

` `

` ` `return` `0;`

`}`

Output:

30

Time Complexity: O(n), where n is the number of nodes in the given binary tree.
Auxiliary Space: O(1)