0144. Preorder Traversal

Easy | Binary Tree + Traversal | 4 ms (99.93%), 13.3 MB (95.41%)

❓ Problem Statement

Source: LeetCode - Binary Tree Preorder Traversal GitHub: Solution / Performance

Given the root of a binary tree, return the preorder traversal of its nodes' values.

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

💡 Ideas

1. Pop the stack to retrieve the current node and append the current node's value

2. Push left-child and then right-child node onto the stack if existing

🤖 Python3

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # (base case)
        if not root: return []
        if not root.left and not root.right: return [root.val]
        
        # ==================================================
        #  Binary Tree + Pre-order Traversal               =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            ans.append(node.val)
            
            if node.right: stack.append(node.right)
            if node.left: stack.append(node.left)
                
        return ans
        
        '''
        # ==================================================
        #  Binary Tree + Pre-order Traversal               =
        # ==================================================
        # time  : O(n)
        # space : O(n)

        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
        '''

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public List<Integer> preorderTraversal(TreeNode root) {
        /* base case */
        if(root == null) return new ArrayList<>();
        
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        
        while(!stack.isEmpty()) {
            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;
    }
}