Devin's Blog

Binary Tree Right Side View

2 min read

TARGET DECK: Leetcode FILE TAGS:

Intuition

  • You can use DFS to keep track of the largest possible height of the tree, similar to Height of a Binary Tree, and then you can use that knowledge to include or not include a node.
  • Alternatively, you can use BFS and simply keep the last node that is on that level.

Code

BFS

# 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:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
 
        res = []
        q = deque([root])
 
        while q:
            n = len(q)
            for i in range(n):
                node = q.popleft()
                if i == n - 1: # Get rightmost node
                    res.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        
        return res

DFS without Nonlocal

# 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:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def r(node, height, max_height):
            if not node:
                return max_height
            if height > max_height:
                res.append(node.val)
            max_height = max(max_height, height)
            max_height = max(max_height, r(node.right, height + 1, max_height))
            max_height = max(max_height, r(node.left, height + 1, max_height))
            return max_height
 
        r(root, 1, 0)
        return res

DFS with Nonlocal

# 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:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        max_height = 0
        def r(node, height):
            nonlocal max_height
            if not node:
                return
            if height > max_height:
                res.append(node.val)
 
            r(node.right, height + 1)
            max_height = max(height, max_height)
            r(node.left, height + 1)
 
        r(root, 1)
        return res

Cards

START Basic Front: Binary Tree Right Side View Back: BFS Binary Tree Level Order Traversal, keeping the rightmost node for each level.

END

References

Graph View