【Video】Recursive Solution and Stack Solution
Intuition\nWe should know how to implement inorder, preorder and postorder.\n\n# Solution Video\n\nhttps://youtu.be/9dTgOlzLDa0\n\n\u25A0 Timeline\n0:09 Explain
# Intuition\nWe should know how to implement inorder, preorder and postorder.\n\n# Solution Video\n\nhttps://youtu.be/9dTgOlzLDa0\n\n\u25A0 Timeline\n`0:09` Explain Recursive Solution\n`1:02` Coding for Recursive Solution\n`2:08` Time Complexity and Space Complexity for Recursive Solution\n`2:27` Explain Stack Solution\n`7:27` Coding for Stack Solution\n`8:46` Time Complexity and Space Complexity for Stack Solution\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 8,338\nThank you for your support!\n\n---\n\n# Solution 1 - Recursive Solution\n\nTo be honest, we should know how to implement inorder, preorder and postorder.\n\n```\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\n\nresult = []\n\ndef inorder(root):\n    if not root:\n        return []\n\n    inorder(root.left)\n    result.append(root.val)\n    inorder(root.right)\n    return result\n\ndef preorder(root):\n    if not root:\n        return []\n\n    result.append(root.val)\n    preorder(root.left)\n    preorder(root.right)\n    return result\n\ndef postorder(root):\n    if not root:\n        return []\n\n    postorder(root.left)\n    postorder(root.right)\n    result.append(root.val)\n    return result\n```\n\nLet\'s focus on `result.append(root.val)`\n\n---\n\n\u2B50\uFE0F Points\n\nFor `Inorder`, we do something `between` left and right.\nFor `Preorder`, we do something `before` left and right.\nFor `Postorder`, we do something `after` left and right.\n\n---\n\nWe use preorder this time, so do something before left and right.\n\nhttps://youtu.be/bU_dXCOWHls\n\n---\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(h)$$\n\n```python []\nclass Solution:\n    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n        res = []\n\n        def preorder(node):\n            if not node:\n                return\n            \n            res.append(node.val)\n            preorder(node.left)\n            preorder(node.right)\n        \n        preorder(root)\n\n        return res\n```\n```javascript []\nvar preorderTraversal = function(root) {\n    const res = [];\n\n    function preorder(node) {\n        if (!node) {\n            return;\n        }\n\n        res.push(node.val);\n        preorder(node.left);\n        preorder(node.right);\n    }\n\n    preorder(root);\n    return res;    \n};\n```\n```java []\nclass Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> res = new ArrayList<>();\n\n        preorder(root, res);\n        return res;        \n    }\n\n    private void preorder(TreeNode node, List<Integer> res) {\n        if (node == null) {\n            return;\n        }\n\n        res.add(node.val);\n        preorder(node.left, res);\n        preorder(node.right, res);\n    }    \n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> res;\n\n        preorder(root, res);\n        return res;        \n    }\n\nprivate:\n    void preorder(TreeNode* node, std::vector<int>& res) {\n        if (node == nullptr) {\n            return;\n        }\n\n        res.push_back(node->val);\n        preorder(node->left, res);\n        preorder(node->right, res);\n    }    \n};\n```\n\n# Step by Step Algorithm\n\n### 1. **Initialization of the Result List**\n   ```python\n   res = []\n   ```\n   - **Explanation:** An empty list `res` is created to store the values of the nodes as they are visited in preorder (root, left, right) traversal order.\n\n### 2. **Definition of the Preorder Function**\n   ```python\n   def preorder(node):\n   ```\n   - **Explanation:** A helper function `preorder` is defined, which takes a `node` as its argument. This function will be used to perform the preorder traversal recursively.\n\n### 3. **Base Case: Check for Null Node**\n   ```python\n   if not node:\n       return\n   ```\n   - **Explanation:** This checks if the current `node` is `None` (i.e., if there is no node to process). If the `node` is `None`, the function returns immediately, effectively ending the recursion for that branch of the tree.\n\n### 4. **Process the Current Node**\n   ```python\n   res.append(node.val)\n   ```\n   - **Explanation:** If the current `node` is not `None`, its value is added to the `res` list. This corresponds to visiting the root node in preorder traversal.\n\n### 5. **Recursive Call to Traverse the Left Subtree**\n   ```python\n   preorder(node.left)\n   ```\n   - **Explanation:** The `preorder` function is called recursively on the left child of the current `node`. This moves the traversal to the left subtree, continuing the preorder pattern.\n\n### 6. **Recursive Call to Traverse the Right Subtree**\n   ```python\n   preorder(node.right)\n   ```\n   - **Explanation:** After the left subtree has been fully traversed, the `preorder` function is called recursively on the right child of the current `node`. This ensures that the right subtree is visited after the left subtree, completing the preorder traversal for this node.\n\n### 7. **Initiating the Preorder Traversal**\n   ```python\n   preorder(root)\n   ```\n   - **Explanation:** The `preorder` function is initially called with the `root` node of the binary tree. This starts the recursive traversal process from the root of the tree.\n\n### 8. **Returning the Result List**\n   ```python\n   return res\n   ```\n   - **Explanation:** After the entire tree has been traversed, the `res` list, now containing all the node values in preorder order, is returned as the output of the `preorderTraversal` function.\n\n---\n\n# Solution 2 - Stack solution\n\nI explain stack solution with visualization in the video above.\n\n```python []\nclass Solution:\n    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n        res = []\n\n        if not root:\n            return res\n        \n        st = [root]\n\n        while st:\n            node = st.pop()\n            res.append(node.val)\n\n            if node.right:\n                st.append(node.right)\n            \n            if node.left:\n                st.append(node.left)\n        \n        return res\n```\n```javascript []\nvar preorderTraversal = function(root) {\n    const res = [];\n    if (!root) return res;\n\n    const stack = [root];\n\n    while (stack.length > 0) {\n        const node = stack.pop();\n        res.push(node.val);\n\n        if (node.right) {\n            stack.push(node.right);\n        }\n        if (node.left) {\n            stack.push(node.left);\n        }\n    }\n\n    return res;    \n};\n```\n```java []\nclass Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> res = new ArrayList<>();\n        if (root == null) return res;\n\n        Stack<TreeNode> stack = new Stack<>();\n        stack.push(root);\n\n        while (!stack.isEmpty()) {\n            TreeNode node = stack.pop();\n            res.add(node.val);\n\n            if (node.right != null) {\n                stack.push(node.right);\n            }\n            if (node.left != null) {\n                stack.push(node.left);\n            }\n        }\n\n        return res;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> res;\n        if (!root) return res;\n\n        stack<TreeNode*> st;\n        st.push(root);\n\n        while (!st.empty()) {\n            TreeNode* node = st.top();\n            st.pop();\n            res.push_back(node->val);\n\n            if (node->right) {\n                st.push(node->right);\n            }\n            if (node->left) {\n                st.push(node->left);\n            }\n        }\n\n        return res;\n    } \n};\n```\n\n# Step by Step Algorithm\n\n### 1. **Initialization of the Result List**\n   ```python\n   res = []\n   ```\n   - **Explanation:** An empty list `res` is created to store the values of the nodes as they are visited in preorder (root, left, right) traversal order.\n\n### 2. **Check if the Root is Null**\n   ```python\n   if not root:\n       return res\n   ```\n   - **Explanation:** This checks if the `root` node is `None` (i.e., the tree is empty). If the `root` is `None`, the function immediately returns the empty `res` list since there\'s nothing to traverse.\n\n### 3. **Initialization of the Stack**\n   ```python\n   st = [root]\n   ```\n   - **Explanation:** A stack `st` is initialized with the `root` node as its only element. The stack will be used to manage the traversal process, simulating the recursive call stack in an iterative manner.\n\n### 4. **Start of the While Loop**\n   ```python\n   while st:\n   ```\n   - **Explanation:** This `while` loop continues to run as long as there are nodes in the stack (`st`). It ensures that the entire tree is traversed.\n\n### 5. **Pop the Top Node from the Stack**\n   ```python\n   node = st.pop()\n   ```\n   - **Explanation:** The top node is popped from the stack, meaning it\'s removed from the stack and assigned to the variable `node`. This is the node that will be processed next.\n\n### 6. **Process the Current Node**\n   ```python\n   res.append(node.val)\n   ```\n   - **Explanation:** The value of the current `node` is added to the `res` list. This corresponds to visiting the root node in the preorder traversal.\n\n### 7. **Push the Right Child onto the Stack**\n   ```python\n   if node.right:\n       st.append(node.right)\n   ```\n   - **Explanation:** If the current `node` has a right child, that right child is pushed onto the stack. This ensures that after the left subtree is processed, the traversal will move to the right subtree.\n\n### 8. **Push the Left Child onto the Stack**\n   ```python\n   if node.left:\n       st.append(node.left)\n   ```\n   - **Explanation:** If the current `node` has a left child, that left child is pushed onto the stack. The left child is pushed after the right child so that it will be processed first (since the stack follows the Last-In-First-Out (LIFO) principle), ensuring the preorder sequence (root, left, right) is maintained.\n\n### 9. **End of the While Loop**\n   - **Explanation:** The loop continues to run, processing each node in the stack in the order they were added, until the stack is empty. This ensures that all nodes are visited in the correct preorder sequence.\n\n### 10. **Return the Result List**\n   ```python\n   return res\n   ```\n   - **Explanation:** After the entire tree has been traversed and all node values have been added to `res`, the `res` list is returned as the final output of the `preorderTraversal` function.\n\n---\n\nThank you for reading my post.\n\u2B50\uFE0F Please upvote it and don\'t forget to subscribe to my channel!\n\n\u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n\u2B50\uFE0F Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### Related video.\n\nBinary Tree Inorder Traversal - LeetCode #94\n\nhttps://youtu.be/TKMxiXRzDZ0\n\n
['Stack', 'Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript']