Leetcode 144. Binary Tree Preorder Traversal
2 min readJan 9, 2023
Intuition
This is a standard tree traversal algorithm where we visit the root, then the left node, and then the right node.
- In order 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, which 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 has n number of nodes, then the time complexity will be O(n). - Space complexity:
We store the maximum number of elements = height of the tree to the stack. So space complexity = O(H) where H = height of the 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);
}
}