Coding

LeetCode Binary Tree Inorder Traversal Solution

0
(0)

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

When we try to understand the problem, it is basically asking for in order traversal of binary tree. I have actually studies all kinds of traversals. So it was actually easy for me this time. If you study the traversals once, you will be able to solve any kind of traversal problems using recursion.

The approach would be to do in order traversal of left element. Then do it for middle element. And then do it for the right element. Use an array to store these. Below is the java code.

class Solution {
    private List<Integer> path = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return path;
        }
        inorderTraversal(root.left);
        path.add(root.val);
        inorderTraversal(root.right);
        return path;
    }
}

And below is the efficiency. So it is the fastest solution ever submitted on LeetCode for this problem. 🙂

Things to keep in mind. Since it is recursion, you need to define the arraylist outside the loop. Think of what to return when the root is null.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments