LeetCode 144: Binary Tree Preorder Traversal Solution

Master LeetCode problem 144 (Binary Tree Preorder Traversal), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

144. Binary Tree Preorder Traversal

Easy

Stack Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To perform a preorder traversal of a binary tree iteratively, we can use a stack to simulate the recursive call stack. The preorder traversal visits the root node first, then recursively visits the left subtree, and finally recursively visits the right subtree.

Here's the step-by-step algorithm:

Initialize an empty stack and a list to store the result.
Push the root node onto the stack.
While the stack is not empty, pop a node from the stack.
Add the node's value to the result list.
If the node has a right child, push the right child onto the stack.
If the node has a left child, push the left child onto the stack.
Repeat steps 3-6 until the stack is empty.

Time complexity: O(n) - where n is the number of nodes in the tree. Space complexity: O(n) - in the worst-case scenario where the binary tree is skewed, the stack can hold all the nodes.

Solution Code

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 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;
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 144 (Binary Tree Preorder Traversal)?

This page provides optimized solutions for LeetCode problem 144 (Binary Tree Preorder Traversal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 144 (Binary Tree Preorder Traversal)?

The time complexity for LeetCode 144 (Binary Tree Preorder Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 144 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 144 in Java, C++, or Python.

Back to LeetCode Solutions