Binary Tree Preorder Traversal

NeetCode: Binary Tree Preorder Traversal · LeetCode: 144. Binary Tree Preorder Traversal · Difficulty: Easy

Given the root of a binary tree, return the preorder traversal of its node values: visit the node itself, then the left subtree, then the right subtree.

Example

Text

Input:  [1, null, 2, 3]     (1 has right child 2, and 2 has left child 3)
Output: [1, 2, 3]

Input:  []
Output: []

Preorder visits every node before its descendants, so it is the natural order for copying or serializing a tree.

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Brute force: recursion

Record the node first, then recurse into the left and right subtrees. The result is a List<Integer>; an ArrayList holds the values in the order they are added.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private void walk(TreeNode node, List<Integer> out) {
        if (node == null) {
            return;
        }
        out.add(node.val);
        walk(node.left, out);
        walk(node.right, out);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        walk(root, out);
        return out;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.preorderTraversal(tree(1, null, 2, 3)));
        System.out.println(s.preorderTraversal(tree(4, 2, 6, 1, 3, 5, 7)));
        System.out.println(s.preorderTraversal(tree()));
    }
}

Output

[1, 2, 3]
[4, 2, 1, 3, 6, 5, 7]
[]

The recursion depth equals the tree height. A chain of many thousands of nodes can overflow the thread's call stack with a StackOverflowError. Time: O(n). Space: O(h) for the call stack.

Optimal: iterative with an explicit stack

Keep a stack of nodes still to visit. Pop a node, record it, then push its right child followed by its left child. Because a stack is last-in-first-out, the left child comes out first, so the whole left subtree is finished before the right one is touched, which is exactly preorder.

ArrayDeque is the stack: push and pop work at the front. It rejects null, so the code pushes a child only when it exists.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root != null) {
            stack.push(root);
        }
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            out.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return out;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.preorderTraversal(tree(1, null, 2, 3)));
        System.out.println(s.preorderTraversal(tree(4, 2, 6, 1, 3, 5, 7)));
        System.out.println(s.preorderTraversal(tree()));
    }
}

Output

[1, 2, 3]
[4, 2, 1, 3, 6, 5, 7]
[]

The stack lives on the heap, so depth is not limited by the thread's call stack. Time: O(n). Space: O(h); the stack holds at most one pending right child per level plus the current node.

Interview points

Preorder is node, left, right. Every node is recorded before its descendants.
The iterative form pushes the right child first so the left child is popped first.
The explicit stack avoids StackOverflowError on very deep trees.

Summary

Time O(n) for both versions.
Recursive space is O(h) on the call stack; iterative space is O(h) on the heap, plus the output.
ArrayDeque does not accept null, so push only existing children.