94. Binary Tree Inorder Traversal — LeetCode(Python)
I got you!
Problem:
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]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 —
Explanation —
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 an inorder traversal, the value of the left child needs to be stored first, then the root node’s value and then the right child’s value.
So, we begin by recursing on the left subtree first.
Then, we append root.val to our answer ans.
After that, we recurse 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 (Method I) —
Explanation —
We use a stack to solve the problem iteratively.
We use 2 while loops to make our life easier. The outer loop can have just a True condition because we are returning from inside this loop.
We need to keep in mind that this is an inorder traversal. So, the left subtree is added first, then the root and then the right subtree.
So, first we traverse the left children of each node we come across and we do this until we reach a leaf node. This is going to be the first node that we add to our inorder path. While traversing, we keep adding these nodes to our stack.
Now, we pop the top element from our stack and add it to our path. And then, we traverse the right subtree because we know that the node and it’s left subtree have been added to our stack already.
When the stack becomes empty, we return our path since we can conclude that every node in the tree has been traversed and added to our path.
Time Complexity —
Since we are visiting every node in the tree a constant number of time, we can say that our algorithm requires a linear amount of time to run.
Also, our stack might be storing all nodes in the tree is the tree is really skewed (like a linked list). So we must assume that we require linear amount of extra space in the worst case.
Thus, if there are n nodes in the binary tree,
Time Complexity: O(n)
Space Complexity: O(n)
3. Iterative (Method II) —
Explanation —
We can use the fact that we need to traverse a node twice — once before we go to it’s left subtree and once after we are done traversing the left subtree.
We keep track of whether a node is visited or not.
So we instead of storing only a node in our stack, we also store a boolean value True/False to represent it’s visited status.
As we iterate through the tree, we keep adding nodes and visited values as a tuple in our stack.
We start by adding the root node with a value False since it has not yet been visited.
Note: We assume a node to be visited when it has been popped out from the stack and not when it is pushed onto the stack.
We now keep popping from the stack.
If the current node is not a NULL node, then we check if it has been visited. If yes, then we append it to our answer. If not, then we append the nodes in the following order:
right → root → left
This time, we change the visited status of our current node to be True.
The while loop terminates when the stack is empty and we have traversed all nodes in the tree. This is when we return our path ans.
Time and Space Complexity —
The complexity analysis is the same as that of Solution 2 above.
Since we are visiting every node in the tree a constant number of time, we can say that our algorithm requires a linear amount of time to run.
Also, our stack might be storing all nodes in the tree is the tree is really skewed (like a linked list). So we must assume that we require linear amount of extra space in the worst case.
Thus, if there are n nodes in the binary tree,
Time Complexity: O(n)
Space Complexity: O(n)
