Leetcode 144. Binary Tree Preorder Traversal

144. Binary Tree Preorder Traversal

Given the root of a binary tree, return the preorder traversal of its nodes' values.

DFS Recursive Approach 1


class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new LinkedList<>();
        if(root == null) return res;
        dfsHelper(root, res);
        return res;
    }
    
    void dfsHelper(TreeNode node, List res){
        if(node != null){
            res.add(node.val);
             dfsHelper(node.left, res);
             dfsHelper(node.right, res);
        }
    }
}

Time and Space Complexity: O(n)

BFS Iterative Approach 2


class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList<>();
        Stack stack = new Stack();
        if (root != null) {
            stack.push(root);
        }
        TreeNode cur;
        while (!stack.empty()) {
            cur = stack.pop();
            res.add(cur.val);            // visit the root
            if (cur.right != null) {
                stack.push(cur.right);          // push right child to stack if it is not null
            }
            if (cur.left != null) {
                stack.push(cur.left);           // push left child to stack if it is not null
            }
        }
        return res;
    }
}

Time and Space Complexity: O(n)

Morris Algo for Preorder Traversal Approach 3:


class Solution{
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        TreeNode current = root;

        while (current != null) {
            if (current.left == null) {
                result.add(current.val);
                current = current.right;
            } else {
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    result.add(current.val);
                    predecessor.right = current;
                    current = current.left;
                } else {
                    predecessor.right = null;
                    current = current.right;
                }
            }
        }
        return result;
    }
}

Time Complexity: O(n) and Space Complexity: O(1)

See Video lecture

Leetcode 102. Binary Tree Level Order Traversal

Introduction

Binary Tree Preorder Traversal is a fundamental tree traversal technique used to visit nodes in a binary tree. It follows the **Root-Left-Right** order, meaning:

Visit the root node first.
Recursively traverse the left subtree.
Recursively traverse the right subtree.

This traversal is particularly useful for scenarios where you need to process the root node before any of its subtrees.

Problem Statement

Given the root of a binary tree, return its preorder traversal as a list of node values.

Example

Consider the binary tree:

The preorder traversal output is:

        [1, 2, 4, 5, 3]

Approach

Preorder traversal is straightforward to implement using recursion, but it can also be implemented iteratively with the help of a stack.

Recursive Solution

The recursive approach follows the natural order of **Root-Left-Right** by making recursive calls for the left and right subtrees after processing the root.

Steps to Solve

If the current node is null, return.
Process the current node (add its value to the result).
Recursively traverse the left subtree.
Recursively traverse the right subtree.

Implementation


import java.util.*;

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

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

class Solution {
    public List preorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        traverse(root, result);
        return result;
    }

    private void traverse(TreeNode node, List result) {
        if (node == null) {
            return;
        }

        result.add(node.val); // Process root
        traverse(node.left, result); // Traverse left subtree
        traverse(node.right, result); // Traverse right subtree
    }
}

Iterative Solution

The iterative solution uses a stack to simulate the recursive call stack. Nodes are processed in the order they would be visited during recursive traversal.

Steps to Solve

Initialize a stack and push the root node.
While the stack is not empty:

Pop a node from the stack and process it (add its value to the result).
Push the right child (if any) onto the stack.
Push the left child (if any) onto the stack.

Implementation


import java.util.*;

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

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

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            result.add(current.val);

            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
Space Complexity: O(h), where h is the height of the tree. This accounts for the recursive call stack or the iterative stack.

Applications of Preorder Traversal

Expression Trees: Generates prefix notation of expressions.
Tree Serialization: Used to serialize a tree into a string representation.
Path Finding: Finds all paths in a tree structure by processing nodes early.

Common Mistakes

Not handling null nodes correctly, which can lead to null pointer exceptions.
Confusing preorder with inorder or postorder traversal.
Failing to initialize the result list in iterative solutions.

Edge Cases

An empty tree (should return an empty list).
A single-node tree (should return a list with only the root value).
An unbalanced tree where nodes exist only on one side.

Sample Outputs

Example 1

Tree:

Preorder traversal:

        [1, 2, 4, 5, 3]

Example 2

Tree:

Preorder traversal:

        [1, 2, 3]

Conclusion

Binary Tree Preorder Traversal is a simple yet powerful method for tree traversal. It is widely used in problems where the root node needs to be processed before its children. Mastering both recursive and iterative implementations provides a strong foundation for tackling advanced tree problems.

For further practice, explore tree problems on LeetCode and GeeksforGeeks.