Binary Tree Inorder Traversal | Leetcode #94 | Medium
In this post I will discuss the solution to the leetcode problem — Binary Tree Inorder Traversal.
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]
Example 4:
Input: root = [1,2]
Output: [2,1]
Example 5:
Input: root = [1,null,2]
Output: [1,2]
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:
Trees are not linear data structures like arrays, lists etc. and hence they can be traversed in multiple ways. In-order traversal is a way of traversal where we visit the tree nodes in this order — left, root, right.
As the problem statement mentions, the recursive solution is trivial and asks to solve it in iterative way. Let’s solve them in both the ways.
- Recursive Solution:
The structure of TreeNode
is mentioned in the comments where it has val
holding the value and left
and right
which are corresponding left and right child nodes.
Here is how the recursive algorithm looks like —
- Create a
List<Integer>
and let’s call itoutput
which will hold the result of in-order traversal. - Create a helper function
traverse()
which we can call recursively by passing aTreeNode
. - Start by calling the
traverse()
function withroot
as the input. - As every recursive function needs a base condition so that the execution stops, in this case we check if the passed
root
is null or not. If it is, then we return an empty list. - Otherwise, call the
traverse()
function withroot.left
which will traverse the left subtree recursively. - Add
root.val
to theoutput
which means we have visited the current node. - Call the
traverse()
function withroot.right
which will traverse the right subtree recursively.
That’s it. That traverses the entire tree in in-order way. Here is how the code looks like —
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<Integer> output = new ArrayList();
public List<Integer> inorderTraversal(TreeNode root) {
return traverse(root);
}
private List<Integer> traverse(TreeNode root) {
if (root == null) {
return new ArrayList();
}
traverse(root.left);
output.add(root.val);
traverse(root.right);
return output;
}
}
2. Iterative Solution:
To traverse the tree in iterative way, we need to take help of another data structure i.e. Stack. As Stack is a last in first out (LIFO) data structure, it perfectly suits our needs to traverse the tree. Let’s see how —
- Create a
List<Integer>
and let’s call itoutput
which will hold the result of in-order traversal. - Create a stack for storing the
TreeNode
and call itstack
. - Create a temporary TreeNode called
current
and initialized it withroot
. - Iterate the tree until the
current
is null OR thestack
is empty. - As we are traversing in-order, we need to keep traversing left until we reach the leaf nodes i.e. the node does not have any children. We can do that by keep pushing the current nodes to the stack and moving current to the left.
- Once we are done with step 5, we get the top most node from the stack i.e.
stack.pop()
which is our newcurrent
node. - Add it to the output.
- Now we need to move to the right subtree and hence assign current to the left node.
- Return the
output
.
This is how the code looks like —
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> output = new ArrayList();
Stack<TreeNode> stack = new Stack();
TreeNode current = root;
while(current != null || !stack.isEmpty()) {
while(current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
output.add(current.val);
current = current.right;
}
return output;
}
}
I hope you enjoyed solving this problem and the solution helps! Happy coding! 🙂
If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.
Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems