algoadvance

Leetcode 144. Binary Tree Preorder Traversal

Problem Statement

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

Clarifying Questions

  1. What is the structure of the binary tree node?
    • The binary tree node is typically defined as: 
      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;
    }
}
  2. Is it guaranteed that the input tree root is not null?
    • No, the root can be null. In that case, the function should return an empty list.
  3. Should we consider iterative solutions, recursive solutions, or both?
    • We can consider both, but a recursive solution is simpler to implement and understand for preorder traversal.

Strategy

The preorder traversal of a binary tree involves visiting the nodes in the following order:

  1. Visit the root node.
  2. Recursively visit the left subtree.
  3. Recursively visit the right subtree.

We’ll implement the preorder traversal using both recursive and iterative methods:

Recursive Solution

  1. Start from the root node.
  2. Append the value of the current node to the result list.
  3. Recursively traverse the left subtree.
  4. Recursively traverse the right subtree.

Iterative Solution

  1. Use a stack to keep track of nodes.
  2. Start from the root node and push it onto the stack.
  3. While the stack is not empty, pop a node, append its value to the result list, and push its right and then its left child onto the stack (this ensures left children are processed first).

Code

Recursive Solution

import java.util.ArrayList;
import java.util.List;

public 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 Solution

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public 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 Complexity

Both the recursive and iterative solutions have a time complexity of O(n), where n is the number of nodes in the binary tree. This is because each node is visited exactly once.

Summary

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI