Binary Tree Preorder Traversal

Problem Statement

In the given task, you are asked to perform a preorder traversal for a binary tree starting from the node referred to as root. During a preorder traversal, the sequence of operations is: Visiting the root node first, then recursively performing a preorder traversal on the left subtree, followed by the right subtree. The aim is to record and return the values of the nodes in the order they are visited. This form of traversal is particularly useful in scenarios like expression tree evaluations and syntax tree traversal, where the root precedence is critical.

Examples

Example 1

Input:

root = [1,null,2,3]

Output:

[1,2,3]

Explanation:

Example 2

Input:

root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output:

[1,2,4,5,6,7,3,8,9]

Explanation:

Example 3

Input:

root = []

Output:

[]

Example 4

Input:

root = [1]

Output:

[1]

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Approach and Intuition

A binary tree preorder traversal involves visiting the nodes in a Root-Left-Right sequence. Here's an intuitive breakdown and a step-by-step explanation for the examples provided:

1. Example 1:

   • Input: root = [1, null, 2, 3]
   • The binary tree is:
     • The root 1 has no left child and a right child 2.
     • The node 2 has left child 3.
   • Preorder traversal visits the root 1, moves to the right child 2, and then to the left child 3 (Root-Right-Left, because no left child for 1).
   • Output: [1, 2, 3]

2. Example 2:

   • Input: root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]
   • The tree structure:
     • 1 is the root, with left child 2 and right child 3.
     • 2 has children 4 (left) and 5 (right). 5 has further children 6 (left) and 7 (right).
     • 3 has right child 8, and 8 has further left child 9.
   • The preorder traversal sequence: 1, then left child 2, continue to deepest left 4, backtrack and go to 5, then to its children 6 and 7, backtrack to 3 and its subtree 8, then 9.
   • Output: [1, 2, 4, 5, 6, 7, 3, 8, 9]

3. Example 3:

   • Input: root = []
   • An empty tree returns an empty list.
   • Output: []

4. Example 4:

   • Input: root = [1]
   • The tree has only one node 1.
   • Output: [1]

These examples illustrate various scenarios from an empty tree to a more densely populated one, showing the practical application of the Root-Left-Right traversal principle inherent in preorder traversals. The consistency observed in this traversal method lends straightforwardness to tasks such as tree serialization and making copies of the tree.

Solutions

class Solution {
public:
    vector<int> traversePreorder(TreeNode* root) {
        vector<int> result;
        TreeNode* current = root;
        while (current != nullptr) {
            if (current->left == nullptr) {
                result.push_back(current->val);
                current = current->right;
            } else {
                TreeNode* temp = current->left;
                while (temp->right != nullptr && temp->right != current) {
                    temp = temp->right;
                }
                if (temp->right == nullptr) {
                    result.push_back(current->val);
                    temp->right = current;
                    current = current->left;
                } else {
                    temp->right = nullptr;
                    current = current->right;
                }
            }
        }
        return result;
    }
};