Harsh Rajpal

Posted on

# 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();

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

return result;
}
}
``````