## Intuition

This is a standard tree traversal algorithm where we visit the root, then left node and then right node.

- Inorder traversal - left root right
- Postorder traversal - left right root

## Approach

- Using Stack :
- Push the root node to the stack.
- Until the stack is not empty, first store the top element of the stack to our result.
Preorder traversal is root -> left -> right.

Since we use stack which is LIFO, we first push the right node to the stack, then push the left node to the stack.Using recursion :

Check whether the node is null and this is the base condition for recursion.

Store the node value to our result.

Visit the left node.

Visit the right node.

## Complexity

Time complexity:

We are going through all the nodes of the tree. If the tree have n number of nodes, then time complexity will be O(n).Space complexity:

We store maximum number of element = height of the tree to the stack. So space complexity = O(H) where H = height of tree

## Code

```
/**
* Definition for a binary tree node.
* 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;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// preorder - root left right
// inorder - left root right
// postorder - left right root
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
byUsingStack(root, result);
byUsingRecursion(root, result);
return result;
}
private void byUsingStack(TreeNode node, List<Integer> result) {
Stack<TreeNode> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
TreeNode top = stack.pop();
result.add(top.val);
if (top.right != null) {
stack.push(top.right);
}
if (top.left != null) {
stack.push(top.left);
}
}
}
private void byUsingRecursion(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val);
byUsingRecursion(node.left, result);
byUsingRecursion(node.right, result);
}
}
```

## Top comments (0)