algoadvance

Leetcode 144. Binary Tree Preorder Traversal

Problem Statement

Leetcode Problem 144: Binary Tree Preorder Traversal

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

In preorder traversal, the nodes are recursively visited in this order:

1. Visit the root node.
2. Traverse the left subtree.
3. Traverse the right subtree.

Example

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

Clarifying Questions

1. What should the output be if the input tree is empty (i.e., root is null)?
   • The output should be an empty list.
2. Are there any constraints on the tree (e.g., maximum number of nodes or node values)?
   • Constraints usually include an upper limit on the number of nodes (let’s assume 0 <= Number of nodes <= 5000) and node values (usually within a variety of integer ranges).

Code

Let’s implement the preorder traversal using a recursive approach.

#include <vector>
using namespace std;

// 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:
    void preorderTraversalHelper(TreeNode* node, vector<int>& traversal) {
        if (node == nullptr) {
            return;
        }
        traversal.push_back(node->val); // Visit the root
        preorderTraversalHelper(node->left, traversal); // Traverse left subtree
        preorderTraversalHelper(node->right, traversal); // Traverse right subtree
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorderTraversalHelper(root, result);
        return result;
    }
};

Strategy

1. Define a helper function preorderTraversalHelper that takes the current node and the traversal list as its arguments.
2. Base Case: In the helper function, if the node is nullptr, return immediately because there is nothing to process.
3. Add the current node’s value to the traversal list.
4. Recursively call the helper on the left subtree.
5. Recursively call the helper on the right subtree.
6. In the preorderTraversal function, initialize an empty vector and call the helper function starting with the root.

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once.
• Space Complexity: O(n) in the worst case for the recursion stack, where the tree is skewed and has a height of n. In the average case (balanced tree), the recursion stack will have depth O(log n). Additionally, the space required for the output list is O(n).

This solution ensures that every node is processed efficiently following the preorder traversal order: root, left, right.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?