Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def preorderTraversal(self, root):
        result = []
        def dfs(node):
            if not node:
                return
            result.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return result
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorder(root, result);
        return result;
    }
private:
    void preorder(TreeNode* node, vector<int>& result) {
        if (!node) return;
        result.push_back(node->val);
        preorder(node->left, result);
        preorder(node->right, result);
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }
    private void preorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        result.add(node.val);
        preorder(node.left, result);
        preorder(node.right, result);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    const result = [];
    function dfs(node) {
        if (!node) return;
        result.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return result;
};
      

Problem Description

You are given the root of a binary tree. Your task is to return the preorder traversal of its nodes' values as a list or array. In preorder traversal, you visit the root node first, then recursively visit the left subtree, followed by the right subtree.

• Each node contains an integer value.
• The tree may be empty (i.e., root is null).
• Return the traversal as a list or array in the order nodes are visited.

Thought Process

When asked to traverse a binary tree in preorder, the first idea is to simply "visit the root, then the left, then the right." This naturally suggests using recursion, since each subtree can be treated as a smaller tree with the same rules. The brute-force approach is to manually keep track of the order, but recursion simplifies this by using the call stack.

Alternatively, if we want to avoid recursion (for example, to prevent stack overflow on very deep trees), we can use an explicit stack to simulate the process.

Both approaches must ensure that every node is visited exactly once, and in the correct order: root, left, right. We also need to handle the case where the tree is empty.

Solution Approach

• 1. Recursive Approach:
  • Start at the root node.
  • If the node is not null, add its value to the result list.
  • Recursively traverse the left subtree.
  • Recursively traverse the right subtree.
  • This is a depth-first traversal that naturally follows the preorder rule.
• 2. Iterative Approach (using a stack):
  • Initialize an empty stack and push the root node (if not null).
  • While the stack is not empty:
    • Pop the top node and add its value to the result.
    • Push the right child (if it exists), then the left child (if it exists) onto the stack.
    • By pushing right before left, we ensure the left is processed first (since stack is LIFO).
• Both approaches ensure every node is visited exactly once, and the values are collected in preorder.

Example Walkthrough

Example Tree:

        1
         \
          2
         /
        3
    

• Start at root: 1. Add 1 to result.
• Left child is null, so move to right child: 2. Add 2 to result.
• Left child of 2 is 3. Add 3 to result.
• 3 has no children, so traversal is complete.

Final preorder traversal: [1, 2, 3]

Time and Space Complexity

• Brute-force / Recursive Approach:
  • Time Complexity: O(N), where N is the number of nodes. Each node is visited exactly once.
  • Space Complexity: O(N) in the worst case (skewed tree), due to the recursion stack and the output list.
• Iterative Approach:
  • Time Complexity: O(N) for the same reason: each node is processed once.
  • Space Complexity: O(N) for the stack in the worst case (all nodes on one side).

Summary

The preorder traversal problem is a classic example of tree traversal, easily solved using recursion or an explicit stack. The key insight is to process nodes in the order: root, left, right. Both recursive and iterative approaches achieve this efficiently, with time and space complexity linear in the number of nodes. This problem demonstrates how breaking a problem into smaller subproblems (recursion) or simulating recursion with a stack can simplify tree algorithms.