Categories
Algorithms

LeetCode#94: Binary Tree Inorder Traversal

First check out the problem description here on LeetCode.

The Solution

This is marked as a medium difficult problem. However if you know what in-order traversal does, it is a very simple problem. Here I just added a helper traverse() method.

All the trick is done in the few lines inside the function. It checks if the current node is null, then it skips. Else it runs the same method recursively on the left child first, then it actually adds the current node’s value to the list called result. Then it proceeds to the right child just like left one.

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        return traverse(root, new ArrayList<Integer>()); 
    }

    private List<Integer> traverse(TreeNode node, List<Integer> result){
        if (node==null) return result;        
        traverse(node.left, result);        
        result.add(node.val);        
        traverse(node.right, result);
        

        
        return result;
        
    }
}

Result

This solution beats 100% of the previous solutions by runtime and 99.62% by memory! Wooho!

Leave a Reply

Your email address will not be published. Required fields are marked *