Description
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
Examples:
Example 1:
Input: root = [1,null,2,3]
Output: [1,2,3]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]Solution in Python
To solve the problem of performing a preorder traversal of a binary tree iteratively, we can use a stack data structure. Preorder traversal follows the order: root, left, right.
- Check if the tree is empty: If the root is
None, we return an empty list. - Initialize a stack: We use a stack to keep track of nodes that we need to process. Initially, we push the root node onto the stack.
- Process the stack: We pop a node from the stack, visit it by adding its value to the result list, then push its right child first (if it exists) and then its left child (if it exists) onto the stack. Pushing the right child first ensures that the left child is processed first, maintaining the correct preorder sequence.
- Repeat until the stack is empty: Continue the process until there are no more nodes to process (i.e., the stack is empty).
Python
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# If the tree is empty, return an empty list
if root is None:
return []
# Initialize the stack with the root node
stack = [root]
# This will store the result of the preorder traversal
result = []
# Process nodes until there are none left in the stack
while stack:
# Pop the top node from the stack
node = stack.pop()
# Visit the node by adding its value to the result list
result.append(node.val)
# Push the right child first so that the left child is processed first
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return resultDetailed Comments:
- Initialization:
stack = [root]: The stack is initialized with the root node.result = []: An empty list to store the preorder traversal result.
- While Loop:
- The loop continues as long as there are nodes in the stack.
node = stack.pop(): The top node is popped from the stack and processed.result.append(node.val): The value of the current node is added to the result list.if node.right is not None: Check if the right child exists; if it does, push it onto the stack.if node.left is not None: Check if the left child exists; if it does, push it onto the stack.
By using the stack, we effectively simulate the call stack used in the recursive approach, ensuring that the nodes are visited in the correct preorder sequence. This iterative method avoids the potential pitfalls of recursion, such as stack overflow for very deep trees.
Solution in Javascript
JavaScript
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
// If the tree is empty, return an empty array
if (root === null) {
return [];
}
// Initialize the stack with the root node
let stack = [root];
// This will store the result of the preorder traversal
let result = [];
// Process nodes until there are none left in the stack
while (stack.length > 0) {
// Pop the top node from the stack
let node = stack.pop();
// Visit the node by adding its value to the result array
result.push(node.val);
// Push the right child first so that the left child is processed first
if (node.right !== null) {
stack.push(node.right);
}
if (node.left !== null) {
stack.push(node.left);
}
}
return result;
};Solution in Java
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// If the tree is empty, return an empty list
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
// Initialize the stack with the root node
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
// Process nodes until there are none left in the stack
while (!stack.isEmpty()) {
// Pop the top node from the stack
TreeNode node = stack.pop();
// Visit the node by adding its value to the result list
result.add(node.val);
// Push the right child first so that the left child is processed first
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
}Solution in C#
C#
using System.Collections.Generic;
public class Solution {
public IList<int> PreorderTraversal(TreeNode root) {
// If the tree is empty, return an empty list
List<int> result = new List<int>();
if (root == null) {
return result;
}
// Initialize the stack with the root node
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
// Process nodes until there are none left in the stack
while (stack.Count > 0) {
// Pop the top node from the stack
TreeNode node = stack.Pop();
// Visit the node by adding its value to the result list
result.Add(node.val);
// Push the right child first so that the left child is processed first
if (node.right != null) {
stack.Push(node.right);
}
if (node.left != null) {
stack.Push(node.left);
}
}
return result;
}
}