Inorder Tree Traversal

Problem

You are given a binary tree represented as childNodes, where node 1 is the root. Write a solution function that performs an inorder 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 inorder traversal, the nodes are visited in the following order:

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

Consider the binary tree shown below:

The inorder traversal begins at the root node, 1, but visits its left subtree first, starting with node 2.

Node 2 also has a left child, 5, so the traversal moves further left.

Since node 5 has no children, it is visited, and then its right subtree is traversed.

Node 4 is visited next as the right child of node 5.

After visiting node 4, the traversal moves back to node 2 and visits it.

Next, the right subtree of node 2 is traversed, starting with node 7.

Within the right subtree of node 7, the left child 6 is visited first.

After visiting node 6, the right child 8 is traversed.

Finally, the traversal returns to the root node 1 and proceeds to its right subtree, visiting node 3.

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

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 section.

Explanation for Test Case 2

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

Explanation for Test Case 3

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