Binary Tree PreOrder Traversal

leetcode.com Problem Statement Given the root of a binary tree, return its preorder traversal. Preorder Traversal follows: Root ↓ Left ↓ Right Brute Force Intuition In an interview, you can explain it like this: Visit the current node first, then recursively traverse the left subtree followed by the right subtree. Recursion naturally follows the preorder sequence. Complexity Time Complexity: O(N) Space Complexity: O(H) Where: N = Number of Nodes H = Height of Tree Recursive Code class Solution { public List < Integer > preorderTraversal ( TreeNode root ) { List < Integer > ans = new ArrayList <>(); preorder ( root , ans ); return ans ; } private void preorder ( TreeNode root , List < Integer > ans ) { if ( root == null ) return ; ans . add ( root . val ); preorder ( root . left , ans ); preorder ( root . right , ans ); } } Moving Towards the Optimal Iterative Approach Instead of recursion, we can use a stack. Since preorder visits: Root ↓ Left ↓ Right we should process the root immediately. To ensure the left subtree is processed first, push the right child before the left child . Pattern Recognition Whenever you see: Preorder Traversal Simulate Recursion Think: Stack Key Observation Stack follows: LIFO To visit: Left First push: Right First ↓ Left Second so that left is popped first. Optimal Java Solution class Solution { public List < Integer > preorderTraversal ( TreeNode root ) { List < Integer > ans = new ArrayList <>(); if ( root == null ) return ans ; Stack < TreeNode > st = new Stack <>(); st . push ( root ); while (! st . isEmpty ()) { TreeNode node = st . pop (); ans . add ( node . val ); if ( node . right != null ) st . push ( node . right ); if ( node . left != null ) st . push ( node . left ); } return ans ; } } Dry Run 1 / \ 2 3 / \ 4 5 Stack: 1 Visit: 1 Push: 3 2 Visit: 2 Push: 5 4 Traversal: 1 ↓ 2 ↓ 4 ↓ 5 ↓ 3 Answer: [1,2,4,5,3] Why Stack Works? A stack processes the most recently added node first. By pushing: Right Child ↓ Left Child the left child