Katkat
Back

Return right and left side views of a tree

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to perform level-order traversal on a binary tree and manipulate the results to extract the boundary nodes.

Binary Tree Side Views

Given the root of a binary tree, return two lists representing the side views of the tree. The 'right side view' consists of the nodes you would see if you were standing on the right side of the tree, ordered from top to bottom. The 'left side view' consists of the nodes visible from the left side, ordered from top to bottom.

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def get_side_views(root: TreeNode) -> tuple[list[int], list[int]]:
    # Returns (left_view, right_view)

Examples

Example 1: Input: root = [1, 2, 3, null, 5, null, 4]

  • Tree structure: 1 /
    2 3 \
    5 4 Output: ([1, 2, 5], [1, 3, 4])

Example 2: Input: root = [1, null, 3] Output: ([1, 3], [1, 3])

Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
  • Consider edge cases like an empty tree or a skewed tree (e.g., all left or all right children).

Note

If a level has only one node, that node should appear in both the left and right side views.

Hints

Hint 1

Perform a level-order traversal using a queue to process the tree one depth level at a time.

Hint 2

For each level, the first node encountered (from the left) is the leftmost node, and the last node encountered is the rightmost node.

Hint 3

If a level contains only one node, that single node serves as both the left and right view for that specific depth.

Follow-up questions

  • How would you modify your solution to return the side view if the tree is extremely wide and you want to optimize for space complexity?
  • Could you solve this using a depth-first search (DFS) approach by passing the current depth level into the recursive function?
  • If the tree were a N-ary tree instead of a binary tree, how would the logic for identifying the 'side' nodes change?