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'll use a recursive approach to implement this.

  1. Base Case: If the root is null (empty tree), return an empty list.
  2. Recursive Step:
    • Add the root's value to the result list.
    • Recursively call the function on the left subtree.
    • Recursively call the function on the right subtree.
  3. Combine Results: Concatenate the results from the root, left subtree, and right subtree into a single list.

Explanation

The recursive approach naturally implements the preorder traversal. The function first visits the root, then recursively traverses the left subtree, and finally, the right subtree. Each recursive call adds the values encountered in the correct preorder sequence. The base case handles the scenario where there are no more nodes to process.

Code

import java.util.ArrayList;
import java.util.List;

/**
 * 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<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        result.add(node.val); //Visit root
        preorderHelper(node.left, result); //Visit left subtree
        preorderHelper(node.right, result); //Visit 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), the height can be equal to N. In the best case (a balanced tree), the height is logâ‚‚N. The space used by the result list is O(N) to store all node values. Therefore, the overall space complexity is dominated by O(N) or O(H) whichever is larger.