Postorder Tree Traversal

Problem

You are given a binary tree represented as childNodes, where node 1 is the root. Write a solution function that performs a postorder traversal of the binary tree and returns the node numbers in the order they are visited.

Concept Explanation

Tree traversal refers to the process of visiting each node in a binary tree in a specific order.
A binary tree is a tree where every node has at most two child nodes, commonly referred to as the left and right child.

In postorder traversal, the nodes are visited in the following order:

1. Recursively traverse the left subtree in postorder.
2. Recursively traverse the right subtree in postorder.
3. Visit the root node.

Consider the binary tree shown below:

The traversal begins at the root node 1. Since postorder traversal requires visiting the left and right subtrees before the root, the algorithm first moves to the left subtree, starting with node 2.

Following the same principle, the traversal continues to the left subtree of node 2, starting with node 5.

Node 5 has no left child, so the traversal moves to its right child, node 4. Since node 4 has no children, it is visited, and the traversal returns to node 5.

After visiting both left and right subtrees of node 5, node 5 is visited, and the traversal returns to node 2.

The traversal then moves to the right subtree of node 2, starting with node 7. Following the same process, it visits nodes 6 and 8 in order.

After completing the traversal of the left subtree of node 1, the algorithm moves to the right subtree, visiting node 3. Finally, node 1 is visited.

Thus, the postorder traversal of the given tree is:
4 → 5 → 8 → 6 → 7 → 2 → 3 → 1.

Constraints

• childNodes is a 2D array representing the left and right child nodes for each node:
  • The length of childNodes is between 2 and 100,000.
  • childNodes[i - 1][0] represents the left child of node i.
  • childNodes[i - 1][1] represents the right child of node i.
  • If a node does not have a left or right child, the corresponding value is -1.

Test Case

Explanation for Test Case 1

• This test case matches the example shown in the concept explanation section.

Explanation for Test Case 2

• Postorder traversal:
  4 → 8 → 10 → 2 → 7 → 5 → 3 → 9 → 6 → 1.

Explanation for Test Case 3

• Postorder traversal:
  3 → 2 → 4 → 5 → 1.