94. Binary Tree Inorder Traversal

Description

The problem is to perform an in-order traversal of a binary tree and return the values of the nodes in a list. In-order traversal visits nodes in the following order: left subtree, current node, right subtree.

Intuition

In an in-order traversal, we start from the root node and recursively visit the left subtree, then process the current node, and finally visit the right subtree. This ensures that nodes are visited in ascending order for a binary search tree, but the approach is general for any binary tree.

Approach

1. Define the Helper Function: - Create a helper function traverse that will perform the recursive traversal. This function takes a node and a list to store the result.
2. Recursive Traversal: - If the node is None, return immediately as there is nothing to process. - Recursively traverse the left subtree of the current node. - Add the current node's value to the result list. - Recursively traverse the right subtree of the current node.
3. Initialize and Call the Helper Function: - In the main method inorderTraversal, initialize an empty list to store the result. - Call the traverse function starting with the root node. - Return the result list which contains the values of nodes in in-order.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once during the traversal.

Space Complexity:

O(h), where h is the height of the binary tree. This space is used for the call stack during recursion. In the worst case (unbalanced tree), the space complexity can be O(n), but in a balanced tree, it is O(log n).

Code

C++

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector result;
        traverse(root, result);
        return result;
    }
private:
    void traverse(TreeNode* node, vector& result) {
        if (!node) return;
        traverse(node->left, result);
        result.push_back(node->val);
        traverse(node->right, result);
    }
};

Python

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def traverse(node: Optional[TreeNode], result: List[int]):
            if node is None:
                return
            traverse(node.left, result)
            result.append(node.val)
            traverse(node.right, result)
        
        result = []
        traverse(root, result)
        return result

Java

class Solution {
    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        traverse(root, result);
        return result;
    }
    
    private void traverse(TreeNode node, List result) {
        if (node == null) {
            return;
        }
        traverse(node.left, result);
        result.add(node.val);
        traverse(node.right, result);
    }
}

JavaScript

var inorderTraversal = function(root) {

    let result = [];
    const traverse = (node) =>{
        if(!node) return;

        traverse(node.left);
        result.push(node.val);
        traverse(node.right);
    }

    traverse(root);
    
    return result;  
};