Binary Tree Preorder Traversal

EASY

Description

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?

Approaches

Checkout 3 different approaches to solve Binary Tree Preorder Traversal. Click on different approaches to view the approach and algorithm in detail.

Recursive Approach

The most intuitive way to perform a preorder traversal is using recursion. The preorder traversal follows the order: Root -> Left -> Right. A recursive function can naturally implement this by processing the current node, then making a recursive call for the left child, followed by a recursive call for the right child.

Algorithm

Create a helper function, say traverse(node, resultList).
If the current node is null, return.
Add the node.val to the resultList (visiting the root).
Recursively call traverse(node.left, resultList) to traverse the left subtree.
Recursively call traverse(node.right, resultList) to traverse the right subtree.

This approach uses a helper function that takes the current node and a list to store the results. The base case for the recursion is when the node is null. Otherwise, it first adds the current node's value to the list, then makes a recursive call on the left child, and finally on the right child. This order of operations perfectly matches the definition of preorder traversal.

/**
 * 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> result) {
        if (node == null) {
            return;
        }
        result.add(node.val);       // Visit the root
        traverse(node.left, result);  // Traverse left subtree
        traverse(node.right, result); // Traverse right subtree
    }
}

Complexity Analysis

Time Complexity: O(N), as each node is visited exactly once.Space Complexity: O(H), where H is the height of the tree. In the worst case of a skewed tree, this is O(N).

Pros and Cons

Pros:

Simple and intuitive to understand and implement.
The code directly reflects the definition of preorder traversal.

Cons:

Can lead to a StackOverflowError for very deep or skewed trees due to the depth of recursion.
The space complexity is dependent on the height of the tree, which can be O(N) in the worst case.

Code Solutions

Checking out 3 solutions in different languages for Binary Tree Preorder Traversal. Click on different languages to view the code.

/** * 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 > ans = new ArrayList <>(); while ( root != null ) { if ( root . left == null ) { ans . add ( root . val ); root = root . right ; } else { TreeNode prev = root . left ; while ( prev . right != null && prev . right != root ) { prev = prev . right ; } if ( prev . right == null ) { ans . add ( root . val ); prev . right = root ; root = root . left ; } else { prev . right = null ; root = root . right ; } } } return ans ; } }

Video Solution

Watch the video walkthrough for Binary Tree Preorder Traversal

Algorithms:

Depth-First Search

Data Structures:

StackTreeBinary Tree

Companies:

Yahoo |