94. Binary Tree Inorder Traversal

 

Binary Tree Inorder Traversal

Problem Description

Given the root of a binary tree, return the in-order 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?

Inorder traversal

• First, visit all the nodes in the left subtree
• Then the root node
• Visit all the nodes in the right subtree

Approach) Stack

(Image from: https://github.com/MisterBooo/LeetCodeAnimation )

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let stack = [];
    let res = [];
    
    while(root !== null || stack.length !== 0) {
        while(root !== null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
}

Complexity 

Time Complexity

Time complexity will be O(n).

Space Complexity
space complexity should also be O(n).

Approach) Recursion

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    const ans = [];
    inorder(root);
    return ans;

    function inorder(root) {
        if (root === null) {
            return;
        }
        inorder(root.left);
        ans.push(root.val);
        inorder(root.right);
    }
};

Complexity 

Time Complexity

Time complexity will be O(n).

Space Complexity
space complexity should also be O(n).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #94. Binary Tree Inorder Traversal

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!