Preorder 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 preorder 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 preorder traversal, the nodes are visited in the following order:

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

Consider the binary tree shown below:

The preorder traversal is as follows:

1. Start at the root node, 1.
   

2. Traverse the left subtree starting with node 2.
   

3. Visit node 5 in the left subtree of node 2.
   

4. Attempt to traverse the left child of node 5. Since it has no left child, move to its right child, node 4.
   

5. After visiting node 4, return to node 2 and traverse its right subtree, starting with node 7.
   

6. Traverse node 7's left child (6) and its right child (8). After finishing the left subtree of node 1, move to its right child, node 3.
   

Thus, the preorder traversal of the given tree is:
1 → 2 → 5 → 4 → 7 → 6 → 8 → 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

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

Explanation for Test Case 3

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