144. Binary Tree Preorder Traversal — LeetCode(Python)
I got you!
Problem:
Given the root of a binary tree, return the preorder traversal of its nodes' values.
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]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Solution:
1. Recursive —
def dfs(root, ans):
if not root:
return None
ans += [root.val]
dfs(root.left, ans)
dfs(root.right, ans)
ans = []
dfs(root, ans)
return ansExplanation —
We can solve this problem very easily using recursion.
We use a helper function for our depth first search (DFS) algorithm.
The base case of the recursive function is when we reach a NULL node, in which case we return None.
Since this is a preorder traversal, the value of the root node needs to be stored first, then the left child’s value and then the right child’s value.
So, we append root.val to our answer ans.
After that, we recurse on the left subtree and then on the right subtree.
Recursion takes care of the rest and we just need to take the recursive leap of faith.
Finally, we return ans.
Time and Space Complexity —
Since we are visiting all nodes a constant number of times, we can say that our algorithm runs in linear time.
Also, the recursion stack might be storing all nodes in the tree in a really skewed tree (like a linked list), so we can say that we require a linear amount of auxiliary space.
Thus, if there are n nodes in the binary tree,
Time Complexity: O(n)
Space Complexity: O(n)
2. Iterative —
if not root:
return None
stack = [root]
ans = []
while stack:
curr = stack.pop()
ans += [curr.val]
if curr.right:
stack += [curr.right]
if curr.left:
stack += [curr.left]
return ansExplanation —
We can use a stack to imitate the recursion in the previous solution, to make our code iterative.
The stack is used to store the nodes that we eventually add in our answer.
Initially, we store the root of the tree. Then, until our stack is non-empty:
- We pop a node from the stack
- We add this node to our answer ans.
- We append the right child to our stack if it exists.
- Then, we append the left child to our stack if it exists.
The reason behind appending the right child before the left child is that stack always pops out the most recently added element and we need to use the left child before the right child.
Finally, we return ans.
Time Complexity —
The complexity analysis is similar to that of the recursive solution.
Since we are visiting all nodes a constant number of times, we can say that our algorithm runs in linear time.
Also, our stack might be storing all nodes in the tree in a really skewed tree (like a linked list), so we can say that we require a linear amount of auxiliary space.
Thus, if there are n nodes in the binary tree,
Time Complexity: O(n)
Space Complexity: O(n)
