Binary Tree Preorder Traversal easy

Problem Statement

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example 1

Input: root = [1,null,2,3] Output: [1,2,3]

Example 2

Input: root = [] Output: []

Steps

The preorder traversal of a binary tree follows the order: Root -> Left -> Right. We can achieve this recursively or iteratively. Here's a breakdown of the recursive approach:

1. Base Case: If the root is nullptr (empty tree), return an empty vector.
2. Recursive Step:
   • Add the root's value to the result vector.
   • Recursively call the function for the left subtree.
   • Recursively call the function for the right subtree.
   • Concatenate the results from the left and right subtrees to the vector containing the root's value.

Explanation

The recursive approach elegantly mirrors the definition of preorder traversal. The function first processes the root node, then recursively handles the left subtree, and finally the right subtree. The recursive calls build up the result vector by adding nodes in the correct preorder sequence.

Code (C++)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorderHelper(root, result);
        return result;
    }

private:
    void preorderHelper(TreeNode* node, vector<int>& result) {
        if (node == nullptr) {
            return;
        }
        result.push_back(node->val); // Process the root
        preorderHelper(node->left, result); // Process the left subtree
        preorderHelper(node->right, result); // Process the right subtree
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
• Space Complexity: O(H) in the worst case, where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log₂N. An iterative solution using a stack would have O(H) space complexity as well.