Binary Tree Preorder Traversal Leetcode Problem 144 [Python Solution]
In this blog post, we will tackle the Binary Tree Preorder Traversal problem, which is Problem 144 on LeetCode.
This problem falls under the category of Trees and is categorized as "Easy." It's a fundamental problem in binary tree traversal that's important for both understanding tree algorithms and preparing for coding interviews.
Problem Overview
The problem statement is as follows:
Question: Given the root of a binary tree, return the preorder traversal of its nodes' values.
Before we dive into the solution, let's understand what "preorder traversal" means.
Preorder traversal is a way to visit nodes in a binary tree.
It starts at the root and explores as far as possible along each branch before backtracking.
The order of traversal is as follows:
- Visit the current node.
- Recursively traverse the left subtree.
- Recursively traverse the right subtree.
Now, let's look at some 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]
Constraints:
- The number of nodes in the tree is in the range [0, 100].
- Node values are within the range -100 to 100.
Understanding Binary Tree Preorder Traversal Constraints
Before we delve into the solution, let's take a closer look at the problem's constraints.
- The Number of Nodes: The problem allows for a range of 0 to 100 nodes in the binary tree.
This means that the tree can be empty (0 nodes), a single node, or contain multiple nodes.
- Node Values: The values of the nodes are within the range of -100 to 100. This constraint implies that the values are integers, and they can be both positive and negative.
Now, let's proceed to solve the problem efficiently using a Python code solution.
Binary Tree Preorder Traversal Python Code Solution
We will provide both a Python code solution and an explanation of the code.
This solution will employ an iterative approach using a stack data structure.
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
cur, stack = root, []
res = []
while cur or stack:
if cur:
res.append(cur.val)
stack.append(cur.right)
cur = cur.left
else:
cur = stack.pop()
return res
Let's break down the code:
- We define a function
preorderTraversalthat takes the root of the binary tree as input.
This function returns a list of integers, which is the preorder traversal of the binary tree.
-
We initialize
curto the root node andstackas an empty list.curkeeps track of the current node, andstackwill help us backtrack efficiently. -
We create an empty list
resto store the result, which will be the preorder traversal of the binary tree. -
We use a
whileloop to iterate until eithercuris non-null orstackis non-empty.
This loop handles the traversal of the tree.
- Inside the loop, we check if
curis non-null.
If it is, we do the following:
– Append the value of the current node (cur.val) to the res list.
This corresponds to visiting the current node.
– Push the right child of the current node onto the stack.
This is done because, in the preorder traversal, we will visit the left subtree first and then the right subtree.
– Update cur to the left child of the current node, as we are moving to the left subtree.
- If
curis null, we execute theelseblock.
In this case, we need to backtrack because we've reached the end of a branch in the tree.
– We pop the last node from the stack and assign it to cur.
This node will be revisited, and we backtrack to it.
This code continues to traverse the tree, adding nodes to the res list in preorder (root, left, right) until the entire tree has been traversed.
Finally, it returns the res list, which contains the preorder traversal of the binary tree.
Time and Space Complexity
Let's analyze the time and space complexity of our solution.
- Time Complexity: The time complexity of this solution is
O(n), where n is the number of nodes in the binary tree.
We visit each node exactly once.
- Space Complexity: The space complexity is
O(h), where h is the height of the binary tree.
In the worst case, for an unbalanced tree, the height could be n, resulting in O(n) space complexity.
For a balanced tree, the height is logarithmic, leading to O(log n) space complexity.
Reasoning Behind Our Approach
The reasoning behind this iterative approach is to mimic the recursive preorder traversal using an explicit stack.
By using a stack, we can simulate the recursion stack and keep track of where we need to backtrack efficiently.
We maintain a cur pointer to keep track of the current node, and a stack to store nodes whose right subtrees we need to visit later.
When cur becomes null, we pop a node from the stack, effectively moving back up the tree.
This approach allows us to visit nodes in the desired order without the need for explicit recursion.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
Related Interview Questions By Category:
Conclusion
In this blog post, we tackled the Binary Tree Preorder Traversal problem, which is Problem 144 on LeetCode.
We provided an efficient Python solution that uses an iterative approach with an explicit stack to simulate the preorder traversal of a binary tree.
Understanding tree traversal algorithms is essential for any aspiring software developer or data structures and algorithms enthusiast.
This problem not only helps you master binary tree traversal but also prepares you for coding interviews, as tree-related questions are commonly asked by top tech companies like Microsoft.
If you found this post helpful, please like and engage to our content.
For more resources to help you prepare for coding interviews and improve your coding skills, check out Auditorical.
Feel free to comment, ask questions, make suggestions, and share this content with others.
Happy coding!🌲🌲
