Posted on by Kalkicode
Code Binary Tree

Find n-th node in postorder traversal of a binary Tree

In a postorder traversal of a binary tree, we visit the left subtree, then the right subtree, and finally the root node.

To find the n-th node in postorder traversal of a binary tree, we need to traverse the tree in postorder and count the nodes as we visit them. Once we have visited n nodes, we can return the value of the node we are currently at as the n-th node.

Find n-th node of post traversal

Here's a step-by-step approach to find the n-th node in postorder traversal:

  1. Traverse the left subtree recursively, counting the nodes as you go.

  2. Traverse the right subtree recursively, counting the nodes as you go.

  3. If you have visited n nodes, return the value of the current node.

  4. If you haven't visited n nodes yet, increment the node count and continue to the parent node.

  5. If you reach the root node and still haven't visited n nodes, then the n-th node does not exist in the tree.

Note that in a binary tree, each node has at most two children, which means that the time complexity of this algorithm is O(n), where n is the number of nodes in the tree.

Program List

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment