Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Binary Tree Preorder Traversal solution and explanation

EasyBinary TreeDepth-First SearchStackTree7 min read76.6% acceptanceUpdated 9 Apr 2026
Asked atGoogleAmazonMicrosoftBloombergMeta
Practise Binary Tree Preorder Traversal
9:36
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - PythonNeetCodeIO · 9:36 · 38K viewsWatch on YouTube
9 more videos on this problem
  1. Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - PythonNeetCodeIO · 9:36 · 38K views
  2. LeetCode 144. Binary Tree Preorder Traversal ITERATIVELY - Interview Prep Ep 76Fisher Coder · 12:37 · 7K views
  3. [Java] Leetcode 144. Binary Tree Preorder Traversal (Iteratively & Recursively) [Binary Tree #1]Eric Programming · 8:19 · 6K views
  4. LeetCode 144. Binary Tree Preorder Traversal RECURSIVELY - Interview Prep Ep 67Fisher Coder · 6:34 · 5K views
  5. LEETCODE 144 (JAVASCRIPT) | BINARY TREE PREORDER TRAVERSALAndy Gala · 8:55 · 4K views
  6. Leetcode 144 Binary Tree Preorder Traversal (Java)TheAnalyticGuy · 2:15 · 1K views
  7. LeetCode 144 Binary Tree Preorder Traversal iterativeleetuition · 10:01 · 786 views
  8. Binary Tree Preorder Traversal | LeetCode #144 | Python 3 with Recursion | Easy to UnderstandCoding With Jaz · 5:44 · 520 views
  9. LeetCode 144. Binary Tree Preorder Traversal - Iterative & Recursive solutions explainedInterviewDose · 5:35 · 298 views
  10. LeetCode - 144. Binary Tree Preorder Traversal | JavaOrkhan Gasanov · 4:24 · 273 views

The problem

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]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [1,2,4,5,6,7,3,8,9]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

Constraints:

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

Follow up: Recursive solution is trivial, could you do it iteratively?

Approach overview

Problem Overview: Given the root of a binary tree, return the preorder traversal of its nodes' values. Preorder traversal processes nodes in the order root → left → right, meaning you visit the current node first, then recursively explore the left subtree followed by the right subtree.

Approach 1: Recursive DFS (Time: O(n), Space: O(h))

This approach directly mirrors the definition of preorder traversal. Start from the root, append its value to the result, recursively traverse the left child, then recursively traverse the right child. The recursion implicitly uses the call stack to track traversal state. The algorithm visits each node exactly once, so the time complexity is O(n), where n is the number of nodes. Space complexity is O(h), where h is the height of the tree due to the recursion stack (worst case O(n) for a skewed tree, O(log n) for balanced trees). This method is concise and ideal when recursion depth is manageable. It relies on Depth-First Search concepts applied to a Binary Tree.

Approach 2: Iterative Traversal Using Stack (Time: O(n), Space: O(h))

The iterative solution simulates the recursion stack using an explicit stack. Push the root node onto the stack. While the stack is not empty, pop the top node, record its value, then push its right child followed by its left child. Pushing the right child first ensures the left child is processed next, preserving preorder order (root → left → right). Each node is pushed and popped at most once, resulting in O(n) time complexity. The stack holds at most O(h) nodes at a time, where h is the tree height. This approach avoids recursion and works well in environments where recursion depth may cause stack overflow.

Recommended for interviews: Interviewers typically expect the recursive DFS solution first because it demonstrates understanding of preorder traversal and tree recursion. The iterative stack approach shows deeper knowledge of how recursion works internally and proves you can convert recursive tree algorithms into iterative ones. Showing both solutions signals strong mastery of tree traversal patterns.

Approach 1: Recursive Approach

The recursive approach naturally aligns with the definition of preorder traversal: visit the root first, then recursively traverse the left subtree, followed by the right subtree.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def preorderTraversal(root):
    result = []
    def preorder(node):
        if not node:
            return
        result.append(node.val)
        preorder(node.left)
        preorder(node.right)
    preorder(root)
    return result
import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }
    
    private void preorder(TreeNode node, List<Integer> res) {
        if (node == null) return;
        res.add(node.val);
        preorder(node.left, res);
        preorder(node.right, res);
    }
}
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void preorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    res.push_back(root->val);
    preorder(root->left, res);
    preorder(root->right, res);
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    preorder(root, res);
    return res;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var preorderTraversal = function(root) {
    const res = [];
    function preorder(node) {
        if (!node) return;
        res.push(node.val);
        preorder(node.left);
        preorder(node.right);
    }
    preorder(root);
    return res;
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void preorder(struct TreeNode* root, int* result, int* count) {
    if (root == NULL) return;
    result[(*count)++] = root->val;
    preorder(root->left, result, count);
    preorder(root->right, result, count);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* result = (int*)malloc(100 * sizeof(int));
    *returnSize = 0;
    preorder(root, result, returnSize);
    return result;
}
using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        List<int> res = new List<int>();
        Preorder(root, res);
        return res;
    }

    private void Preorder(TreeNode node, List<int> res) {
        if (node == null) return;
        res.Add(node.val);
        Preorder(node.left, res);
        Preorder(node.right, res);
    }
}

Python makes use of a nested helper function for the recursive traversal, adding node values directly to a list. The solution is concise and functional.

Complexity

Time Complexity: O(N), as all nodes are visited exactly once. Space Complexity: O(N), mainly due to recursive call stack depth.

Try this approach in the editor

Approach 2: Iterative Approach using Stack

The iterative approach replaces the recursive call stack with an explicit stack. Nodes are processed in preorder, using a stack to maintain traversal state.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def preorderTraversal(root):
    if not root:
        return []
    stack, result = [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
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stk = new Stack<>();
        stk.push(root);
        while (!stk.isEmpty()) {
            TreeNode node = stk.pop();
            res.add(node.val);
            if (node.right != null) stk.push(node.right);
            if (node.left != null) stk.push(node.left);
        }
        return res;
    }
}
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        res.push_back(node->val);
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
    return res;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var preorderTraversal = function(root) {
    if (!root) return [];
    const res = [];
    const stack = [root];
    while (stack.length) {
        const node = stack.pop();
        res.push(node.val);
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    return res;
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode** stack;
int top = -1;

void push(struct TreeNode* node) {
    stack[++top] = node;
}

struct TreeNode* pop() {
    return stack[top--];
}

int isEmpty() {
    return top == -1;
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    stack = (struct TreeNode**)malloc(100 * sizeof(struct TreeNode*));
    int* result = (int*)malloc(100 * sizeof(int));
    *returnSize = 0;
    push(root);
    while (!isEmpty()) {
        struct TreeNode* node = pop();
        result[(*returnSize)++] = node->val;
        if (node->right) push(node->right);
        if (node->left) push(node->left);
    }
    free(stack);
    return result;
}
using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        List<int> res = new List<int>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);
        while (stack.Count > 0) {
            TreeNode node = stack.Pop();
            res.Add(node.val);
            if (node.right != null) stack.Push(node.right);
            if (node.left != null) stack.Push(node.left);
        }
        return res;
    }
}

The Python code provides an efficient stack-based traversal, eliminating the need for recursion. Nodes are managed within the stack, facilitating straightforward traversal logic.

Complexity

Time Complexity: O(N). Space Complexity: O(N), primarily from stack data.

Try this approach in the editor

Approach 3: Recursive Traversal

We first visit the root node, then recursively traverse the left and right subtrees.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree. The space complexity mainly depends on the stack space used for recursive calls.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function preorderTraversal(root: TreeNode | null): number[] {
    const ans: number[] = [];
    const dfs = (root: TreeNode | null) => {
        if (!root) {
            return;
        }
        ans.push(root.val);
        dfs(root.left);
        dfs(root.right);
    };
    dfs(root);
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) (ans []int) {
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		ans = append(ans, root.Val)
		dfs(root.Left)
		dfs(root.Right)
	}
	dfs(root)
	return
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, ans: &mut Vec<i32>) {
        if root.is_none() {
            return;
        }
        let node = root.as_ref().unwrap().borrow();
        ans.push(node.val);
        Self::dfs(&node.left, ans);
        Self::dfs(&node.right, ans);
    }

    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans = vec![];
        Self::dfs(&root, &mut ans);
        ans
    }
}
Try this approach in the editor

Approach 4: Stack Implementation for Non-Recursive Traversal

The idea of using a stack to implement non-recursive traversal is as follows:

  1. Define a stack stk, and first push the root node into the stack.
  2. If the stack is not empty, pop a node from the stack each time.
  3. Process the node.
  4. First push the right child of the node into the stack, then push the left child of the node into the stack (if there are child nodes).
  5. Repeat steps 2-4.
  6. Return the result.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree. The space complexity mainly depends on the stack space.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function preorderTraversal(root: TreeNode | null): number[] {
    const ans: number[] = [];
    if (!root) {
        return ans;
    }
    const stk: TreeNode[] = [root];
    while (stk.length) {
        const { left, right, val } = stk.pop();
        ans.push(val);
        right && stk.push(right);
        left && stk.push(left);
    }
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) (ans []int) {
	if root == nil {
		return
	}
	stk := []*TreeNode{root}
	for len(stk) > 0 {
		node := stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		ans = append(ans, node.Val)
		if node.Right != nil {
			stk = append(stk, node.Right)
		}
		if node.Left != nil {
			stk = append(stk, node.Left)
		}
	}
	return
}
Try this approach in the editor

Approach 5: Morris Preorder Traversal

Morris traversal does not require a stack, and its space complexity is O(1). The core idea is:

Traverse the binary tree nodes,

  1. If the left subtree of the current node root is empty, add the current node value to the result list ans, and update the current node to root.right.
  2. If the left subtree of the current node root is not empty, find the rightmost node pre of the left subtree (which is the predecessor of the root node in inorder traversal):
    • If the right subtree of the predecessor node pre is empty, add the current node value to the result list ans, then point the right subtree of the predecessor node to the current node root, and update the current node to root.left.
    • If the right subtree of the predecessor node pre is not empty, point the right subtree of the predecessor node to null (i.e., disconnect pre and root), and update the current node to root.right.
  3. Repeat the above steps until the binary tree node is null, and the traversal ends.

The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function preorderTraversal(root: TreeNode | null): number[] {
    const ans: number[] = [];
    while (root) {
        const { left, right, val } = root;
        if (!left) {
            ans.push(val);
            root = right;
        } else {
            let prev = left;
            while (prev.right && prev.right != root) {
                prev = prev.right;
            }
            if (!prev.right) {
                ans.push(val);
                prev.right = root;
                root = root.left;
            } else {
                prev.right = null;
                root = root.right;
            }
        }
    }
    return ans;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) (ans []int) {
	for root != nil {
		if root.Left == nil {
			ans = append(ans, root.Val)
			root = root.Right
		} else {
			prev := root.Left
			for prev.Right != nil && prev.Right != root {
				prev = prev.Right
			}
			if prev.Right == nil {
				ans = append(ans, root.Val)
				prev.Right = root
				root = root.Left
			} else {
				prev.Right = nil
				root = root.Right
			}
		}
	}
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Approach

Time Complexity: O(N), as all nodes are visited exactly once. Space Complexity: O(N), mainly due to recursive call stack depth.

Iterative Approach using Stack

Time Complexity: O(N). Space Complexity: O(N), primarily from stack data.

Recursive Traversal–
Stack Implementation for Non-Recursive Traversal–
Morris Preorder Traversal–

Complexity analysis

ApproachTimeSpaceWhen to Use
Recursive DFSO(n)O(h)Best for clarity and when recursion depth is safe. Mirrors preorder definition.
Iterative Using StackO(n)O(h)Preferred when avoiding recursion or when explicit control of traversal stack is needed.

Frequently asked questions

Is Binary Tree Preorder Traversal easy or hard?

Binary Tree Preorder Traversal is classified as an easy problem because the algorithm directly follows the preorder definition. The main challenge is understanding tree traversal order and translating it into recursive or stack-based code.

Binary Tree Preorder Traversal Python/Java solution

Python and Java solutions typically implement either recursive DFS or an iterative stack approach. Both versions run in O(n) time and O(h) space. The recursive solution is shorter, while the iterative version gives explicit control over the traversal stack.

How to solve Binary Tree Preorder Traversal in O(n)?

Traverse the tree using Depth-First Search and process nodes in root → left → right order. Append the node value when first visiting the node, then explore its left subtree followed by the right subtree. Each node is processed once, resulting in O(n) time complexity.

What is the best approach for Binary Tree Preorder Traversal?

Depth-First Search using recursion is the most common approach because preorder traversal naturally follows the pattern root → left → right. The recursive solution visits each node once with O(n) time and O(h) space, where h is the tree height. An iterative stack-based solution is equally optimal and often preferred when avoiding recursion.

Is Binary Tree Preorder Traversal asked at Google/Amazon/Meta?

Binary tree traversal problems frequently appear in interviews at companies like Amazon, Google, Meta, and Microsoft. While the exact problem may vary, understanding preorder, inorder, and postorder traversal is considered a fundamental tree concept tested in coding interviews.

What data structure is used in Binary Tree Preorder Traversal?

The recursive solution relies on the call stack to manage traversal state. The iterative approach explicitly uses a stack data structure to simulate recursion and ensure nodes are processed in root → left → right order.

What is the time complexity of Binary Tree Preorder Traversal?

Binary Tree Preorder Traversal runs in O(n) time because every node in the tree is visited exactly once. Both recursive DFS and iterative stack implementations achieve this complexity. Space complexity is O(h), where h represents the height of the tree due to recursion or stack storage.

Comments

Next problem · similarBinary Tree Inorder TraversalEasy
Now write it yourselfClose this page and solve Binary Tree Preorder Traversal in the editor, without looking.
Practise Binary Tree Preorder Traversal