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: []

Example 3:

Input: root = [1]
Output: [1]

Steps

The preorder traversal of a binary tree follows the order: Root -> Left -> Right. We'll implement this using recursion or iteration. For this solution, we'll demonstrate both approaches.

Recursive Approach Explanation

The recursive approach is arguably more elegant and easier to understand. The function PreorderTraversalRecursive does the following:

1. Base Case: If the root is null (empty subtree), return an empty list.
2. Recursive Step: Add the root's value to the result list. Recursively call PreorderTraversalRecursive on the left subtree and append the result. Then, recursively call it on the right subtree and append the result.

Iterative Approach Explanation

The iterative approach uses a stack to mimic the recursive calls.

1. Initialization: Initialize an empty stack and an empty result list. Push the root onto the stack.
2. Iteration: While the stack is not empty:
   • Pop the top node from the stack.
   • Add its value to the result list.
   • Push the right child (if it exists) onto the stack.
   • Push the left child (if it exists) onto the stack. (Note the order: right then left to maintain preorder).
3. Return: Return the result list.

Code (C#)

using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    //Recursive Approach
    public IList<int> PreorderTraversalRecursive(TreeNode root) {
        IList<int> result = new List<int>();
        PreorderHelper(root, result);
        return result;
    }

    private void PreorderHelper(TreeNode node, IList<int> result) {
        if (node == null) return;
        result.Add(node.val);
        PreorderHelper(node.left, result);
        PreorderHelper(node.right, result);
    }

    //Iterative Approach
    public IList<int> PreorderTraversalIterative(TreeNode root) {
        IList<int> result = new List<int>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root != null) stack.Push(root);

        while (stack.Count > 0) {
            TreeNode node = stack.Pop();
            result.Add(node.val);
            if (node.right != null) stack.Push(node.right);
            if (node.left != null) stack.Push(node.left);
        }
        return result;
    }
}

Complexity

Recursive Approach:

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be N.

Iterative Approach:

• Time Complexity: O(N)
• Space Complexity: O(H). The space used by the stack is proportional to the height of the tree. In the worst case (a skewed tree), this could be O(N).

Both approaches have the same time and space complexity. The iterative approach might be slightly more efficient in practice because it avoids the overhead of recursive function calls, but the difference is often negligible unless dealing with extremely large trees. The recursive approach is often preferred for its readability and conciseness.