Tech Blogs LLD SDE Playbook DSA

Binary Tree Preorder Traversal

Easy Top 250
Associated Patterns
Trees
Interviewed At (Company Tags)
GoogleAmazonMicrosoft
External Reference View on LeetCode

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]

Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Root, Left, Right Traversal Order

Preorder traversal visits a binary tree in the order: Root Node -> Left Subtree -> Right Subtree. We can solve this:

  1. Recursively: Visit the root node, and then call the helper recursively on the left child followed by the right child.
  2. Iteratively: Use a stack. Push the root node onto the stack. While the stack is not empty, pop the top node, record its value, and then push its children. Note that because a stack is LIFO (Last-In, First-Out), we must push the right child first and then the left child, ensuring the left child is popped and processed first.

Solution 1: Recursive Preorder Traversal

Record parent node value first, then recurse down left and right children.

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

    private void traverse(TreeNode node, List<Integer> list) {
        if (node == null) return;
        list.add(node.val);          // root
        traverse(node.left, list);   // left
        traverse(node.right, list);  // right
    }
}
# 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: Optional[TreeNode]) -> list[int]:
        result = []
        
        def traverse(node: Optional[TreeNode]):
            if not node:
                return
            result.append(node.val) # root
            traverse(node.left)    # left
            traverse(node.right)   # right

        traverse(root)
        return result
#include <vector>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
private:
    void traverse(TreeNode* node, std::vector<int>& list) {
        if (!node) return;
        list.push_back(node->val);
        traverse(node->left, list);
        traverse(node->right, list);
    }

public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> result;
        traverse(root, result);
        return result;
    }
};

Complexity Analysis

  • Time Complexity: O(n) since we visit every node exactly once.
  • Space Complexity: O(h) auxiliary space where h is the tree height, representing the recursion stack depth.

Solution 2: Iterative Traversal using Stack

Explicit stack iteration, pushing right children onto the stack before left children.

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

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            result.add(curr.val); // process root

            // Push right child first, so left child is popped first
            if (curr.right != null) {
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }
        }
        return result;
    }
}
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        result = []
        if not root:
            return result
            
        stack = [root]
        while stack:
            curr = stack.pop()
            result.append(curr.val)
            
            # Push right first so left is processed first
            if curr.right:
                stack.append(curr.right)
            if curr.left:
                stack.append(curr.left)
                
        return result
#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;

        std::stack<TreeNode*> stack;
        stack.push(root);

        while (!stack.empty()) {
            TreeNode* curr = stack.top();
            stack.pop();
            result.push_back(curr->val);

            if (curr->right) {
                stack.push(curr->right);
            }
            if (curr->left) {
                stack.push(curr->left);
            }
        }
        return result;
    }
};

Complexity Analysis

  • Time Complexity: O(n) since we process every node once.
  • Space Complexity: O(h) auxiliary space to store nodes in the stack, where h is the tree height.

← All Problems