144. Binary Tree Preorder Traversal

Problem Statement:
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]

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [1]
Output: [1]

Constraints:

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

Solution:
Algorithm:

1. Create an arraylist and a stack.
2. If the node is null return the arraylist.
3. Add the node to stack.
4. Run a while loop till the stack is not empty.

• Pop the node and add it to the list.
• If right node is not null add it to the stack.
• If left node is not null add it to the the stack
  1. Return the arraylist.

Code:

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

        if (root == null) {
            return result;
        }

        stack.push(root);
        while (!stack.empty()) {
            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;
    }
}