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 pattern: Root -> Left -> Right. This means we visit the root node first, then recursively traverse the left subtree, and finally, recursively traverse the right subtree.

Explanation

1. Base Case: If the root is null (empty tree), return an empty array.

2. Recursive Step:

   • Create an array result to store the preorder traversal.
   • Add the root's value to result.
   • Recursively call the preorderTraversal function on the left subtree and append the returned array to result.
   • Recursively call the preorderTraversal function on the right subtree and append the returned array to result.
   • Return the result array.

Code

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number;
 *     left: TreeNode | null;
 *     right: TreeNode | null;
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function preorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];

    function traverse(node: TreeNode | null) {
        if (node === null) {
            return;
        }
        result.push(node.val);
        traverse(node.left);
        traverse(node.right);
    }

    traverse(root);
    return result;
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node 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), the height can be equal to N. In the best case (a balanced tree), the height is log₂(N). If we use an iterative approach with a stack, the space complexity would also be O(H).