Leetcode 144. Binary Tree Preorder Traversal

Photo by Niko photos on Unsplash

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 :

1. Push the root node to the stack.
2. Until the stack is not empty, first store the top element of the stack to our result.
3. 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 :

1. Check whether the node is null, which is the base condition for recursion.
2. Store the node value to our result.
3. Visit the left node.
4. 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);
    }
}