144. Binary Tree Preorder Traversal

Easy

Problem Description

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

Examples

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

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [1]
Output: [1]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

Java Solution


class Solution {
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Stack stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            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;
    }
}

C++ Solution


class Solution {
public:
    vector preorderTraversal(TreeNode* root) {
        vector result;
        if (!root) {
            return result;
        }
        
        stack stack;
        stack.push(root);
        
        while (!stack.empty()) {
            TreeNode* node = stack.top();
            stack.pop();
            result.push_back(node->val);
            if (node->right) {
                stack.push(node->right);
            }
            if (node->left) {
                stack.push(node->left);
            }
        }
        
        return result;
    }
};

JavaScript Solution


/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    if (!root) {
        return [];
    }
    
    const result = [];
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
    }
    
    return result;
};

C# Solution


public class Solution {
    public IList PreorderTraversal(TreeNode root) {
        IList result = new List();
        if (root == null) {
            return result;
        }
        
        Stack stack = new Stack();
        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 Analysis

Solution Explanation

This solution uses an iterative approach with a stack:

Key points: