LeetCode 199. Binary Tree Right Side View constant memory complexity

Question

I'm trying to solve LeetCode 199.

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

I've already solved this problem by using Level-Order-Traversal with time complexity of O(n) & memory complexity of O(n).

I'm wondering if it's possible to optimize the solution, and solve this problem iteratively with constant memory complexity of O(1) without using any data structure.

My solution with time & memory of O(n):

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # time complexity: O(n), memory complexity: O(n)
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = []
        q = collections.deque([root])
        while q:
            len_q, level = len(q), []
            for _ in range(len_q):
                node = q.popleft()
                level.append(node)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            res.append(level[-1].val) # add the last element of each level (right most element)
        return res

You cannot traverse a tree in O(1) memory unless you are willing to temporarily modify the tree a la Morris traversal. — n. m. could be an AI
– n. m. could be an AI, Commented Aug 18 at 6:22
If you've "already seen tree solutions with constant memory complexity of O(1)" then why are you still "wondering if it is possible to do"? — Kelly Bundy
– Kelly Bundy, Commented Aug 18 at 6:38
Just to come back to extending the tree with pointers to siblings: if these are added references (while still maintaining the left/right references), it is not an O(1) operation, as you would allocate an extra O(1) for each node. If however, you reuse the left/right references for another purpose (like linking to siblings), it is fine. — trincot
– trincot, Commented Aug 18 at 11:56

trincot · Accepted Answer · 2025-08-18 11:00:56Z

6

The memory allocated for the output can be used as a stack to trace the state of the depth-first traversal. Although that is O(n), this is memory that was needed anyway for the output. Besides that there is only O(1) of auxiliary memory used.

Some specifics about that stack:

If a node has two children, then put the node (reference) on the stack so to indicate we later still need to visit its right child
If a node has just one child, then put the node's value on the stack so we know there are no other children to visit, and this value can serve as part of the output
Whenever you pop from the stack, only modify a stack index, but don't actually remove the popped value from the list that backs this stack. That way, that list retains the expected values, even as the stack is emptied.

Here is how you could implement that:

"""
A stack implementation that never really deletes values as we pop, 
but only adjusts a size attribute. 
This way the backing list will retain for each depth the last value 
that was on the stack at that depth.
""" 
class Stack(list):
    def __init__(self):
        super().__init__()
        self.size = 0
    
    def push(self, value):
        if len(self) == self.size:
            self.append(value)
        else:
            self[self.size] = value
        self.size += 1

    def pop(self):
        if self.size:
            self.size -= 1
            return self[self.size]

class Solution:
    def rightSideView(self, node: Optional[TreeNode]) -> List[int]:
        stack = Stack()
        while True:
            # Follow path down the tree to the left-most leaf
            while node:
                stack.push(node if node.left and node.right else node.val)
                node = node.left or node.right
            # Backtrack up the tree to a node whose second child has not been explored
            node = stack.pop()
            while node is not None and not isinstance(node, TreeNode):
                node = stack.pop()
            if node is None:  # all done
                return stack  # this is a list of values overloaded with a size attribute
            # Go down into the right subtree
            stack.push(node.val)
            node = node.right

answered Aug 18 at 11:00

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Magnus Man Nov 14 at 21:50

but is that considered constant memory in terms of big-o?

trincot Nov 15 at 6:50

Most often the memory allocated for the output is included in the space complexity analysis. In this particular challenge, the output size could be O(𝑛) -- when all nodes are visible from the right side -- which then means you cannot hope for a better (worst-case) space complexity than O(𝑛). But in comments, the asker clarified that they are only concerned with the auxiliary space used, without considering the memory that needs to be allocated for the output list. Then indeed this is constant memory in terms of big-O. But it's atypical to exclude the output space.

Collectives™ on Stack Overflow

LeetCode 199. Binary Tree Right Side View constant memory complexity

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related