Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

var inorderTraversal = function(root) {
    //recursive approach
    let result=[];
    if (root===null) {
        return result;
    }
    //go left node
    if (root.left) {
        result=result.concat(inorderTraversal(root.left));
    }
    console.log("adding ", root.val);
    result=result.concat([root.val]);
    if (root.right) {
        result=result.concat(inorderTraversal(root.right));
    }
    //console.log("result ",result);
    return result;
};

Approaches
Inorder traversal of a Binary Tree is a depth-first search (DFS) traversal, where the left bottom most element is the starting point and it goes from left to right at the lowest depths first. There are two approaches to doing this, one recursive and one iterative. We’ll look at the recursive approach here first.

Inorder traversal strategy for recursive is:

• Recurse on left node
• Action on current node
• Recurse on right node

Code Breakdown
Let’s go over the solution block by block and explain as we go.

    let result=[];
    if (root===null) {
        return result;
    }

We initialize the result variable to be an empty array. This will make sense later once you see what we do with the return value from the recursive calls.
The stopping condition for this recursion is when root is null. This means we’re passed a child node that doesn’t exist. We return an empty array in this case.

    //go left node
    if (root.left) {
        result=result.concat(inorderTraversal(root.left));
    }
    console.log("adding ", root.val);
    result=result.concat([root.val]);
    if (root.right) {
        result=result.concat(inorderTraversal(root.right));
    }
    //console.log("result ",result);
    return result;

Recall how we said we recurse left side, process current node, and recurse right side. That’s exactly what we’re doing here.
If the left child exists, we call inorderTraversal on that left child. The return result is an array that we concatenate onto our result array (previously initialized as an empty array). This has the same effect as initializing an array to be the return result of the recursive call but we’re doing it the way shown here to 1) keep the code uniform between left and right children processing, 2) makes our return under terminal condition a variable rather than just an empty array since we initialized up top and 3) doesn’t need to conditional on if result isn’t initialized (for example if left child is null).
Now we process the current node. In this case we just add it to the result array via concatenation. The general strategy is here is where we “process” the node.
And finally we recurse on the right child in the same manner as we did the left child.
We return the result array, that now contains all the elements from the left branch, the current element, and the right branch.