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

• Gerwerus: Have you checked other leetcode solutions?
• n. m. could be an AI: You cannot traverse a tree in O(1) memory unless you are willing to temporarily modify the tree a la Morris traversal.
• Kelly Bundy: 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"?
• n. m. could be an AI: Yes this modification may lead to a solution.
• trincot: 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.

Answer 1

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