Preorder Traversal

Dec 18, 2024 • 4 mins read
Hero Image

Problem Overview

The problem titled "Binary Tree Preorder Traversal" on LeetCode is a classic exercise in understanding tree traversal algorithms. The task is to return the preorder traversal of a binary tree's nodes' values.

A binary tree is a data structure in which each node has at most two children, referred to as the left child and the right child. Preorder traversal is a method of processing the nodes of the tree in a specific order:

  1. Visit the root node.
  2. Traverse the left subtree.
  3. Traverse the right subtree.

Understanding the Problem

Given the root of a binary tree, the objective is to perform a preorder traversal. For instance, given a binary tree:

    1
   / \
  2   3
 / \
4   5

The preorder traversal would visit nodes in the following sequence: 1 -> 2 -> 4 -> 5 -> 3.

Constraints:

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

Key DSA Concepts and Theory

Binary Tree

A binary tree is a hierarchical structure comprising nodes, with each node having at most two children. It's a foundational concept for many advanced data structures and is widely used in various applications.

Tree Traversal

Tree traversal is an algorithmic technique to visit all nodes in a tree systematically. There are various types of tree traversal methods:

  • Preorder Traversal (Root, Left, Right): Visit the current node before its children.
  • Inorder Traversal (Left, Root, Right): Visit the left subtree, the node, and then the right subtree.
  • Postorder Traversal (Left, Right, Root): Visit the children before the node itself.

Preorder traversal is particularly useful for copying the tree structure or prefix expressions for parsing expressions.

Solution Approach

Recursive Approach

The recursive approach to preorder traversal is straightforward. Here's how you can implement it:

  1. Base Case: If the node is null, return an empty list.
  2. Recursive Case:
    • Prepend the current node's value to the traversal list.
    • Recursively visit the left subtree, followed by the right subtree.

Code Implementation

C++ Implementation

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorderHelper(root, result);
        return result;
    }
    
    void preorderHelper(TreeNode* node, vector<int> &result) {
        if (!node) return;
        result.push_back(node->val);
        preorderHelper(node->left, result);
        preorderHelper(node->right, result);
    }
};

Java Implementation

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderHelper(root, result);
        return result;
    }
    
    private void preorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) return;
        result.add(node.val);
        preorderHelper(node.left, result);
        preorderHelper(node.right, result);
    }
}

Iterative Approach

The iterative solution uses a stack data structure to mimic the function call stack in a recursive solution:

  1. Initialize the stack and push the root node to it.
  2. Loop until the stack is empty:
    • Pop a node from the stack, add its value to the output list.
    • Push the right child first, then the left child, to ensure the left subtree is processed first.

C++ Implementation

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) return result;

        stack<TreeNode*> s;
        s.push(root);

        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            result.push_back(node->val);

            if (node->right) s.push(node->right);
            if (node->left) s.push(node->left);
        }
        
        return result;
    }
};

Java Implementation

class Solution {
    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;
    }
}

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the binary tree. Every node is visited exactly once.
  • Space Complexity:
    • For the recursive solution, the space complexity would be O(h) where h is the height of the tree due to the recursion call stack.
    • For the iterative solution, the space complexity is O(n) as we might store all nodes in the stack in the worst case scenario of a completely unbalanced tree.

Common Mistakes to Avoid

  • Not handling the base case where the tree is empty.
  • Pushing nodes onto the stack in the wrong order, particularly in iterative solutions.
  • Failing to manage recursive stack depth, leading to stack overflow for very deep trees, though it's not a concern within given constraints.

Similar Problems on Leetcode

Additional Resources and References

This comprehensive guide offers a detailed walkthrough of the Binary Tree Preorder Traversal problem, its solutions, and related concepts. Understanding these fundamentals will help in tackling similar problems efficiently.