Problem Statement in English

You’re given the root of a binary tree. Return the inorder traversal of its nodes’ values.

Approach

I went with a recursive approach to solve this problem.

The idea is to traverse the left subtree, visit the root node, and then traverse the right subtree. This can be done using a depth-first search (DFS) strategy.

And we’re done!

Step 1: Calculate if a k allows Koko to eat piles within h hours

  • Step 1.1: Calculate hours taken to eat piles[i] for a given k

Solution in Python


class Solution:
    def inorderTraversal(self, root: TreeNode | None) -> list[int]:
        res = []

        def dfs(node):
            if not node:
                return

            if node.left:
                dfs(node.left)

            if node:
                res.append(node.val)

            if node.right:
                dfs(node.right)

        dfs(root)

        return res

Complexity

  • Time: $O(n)$
    Since we visit each node exactly once, the time complexity is linear with respect to the number of nodes in the tree.

  • Space: $O(h)$
    where $h$ is the height of the tree. In the worst case, the space complexity can be $O(n)$ for a skewed tree, but for a balanced tree, it will be $O(\log n)$.

And we are done.