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

Software Development
#1

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)