Implement right side view and local minimum search

Q: Implement right side view and local minimum search

This question evaluates a candidate's understanding of binary tree traversal and array local-minimum detection, measuring skills in data structures (binary trees and arrays), algorithm design, and algorithmic time-complexity analysis.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Question

##### Question

LeetCode 199. Binary Tree Right Side View — Given the root of a binary tree, return the values of the nodes you can see ordered from top to bottom when the tree is viewed from the right side. Given an unsorted array of distinct integers, design an algorithm that returns the index of any local minimum (an element strictly smaller than its immediate neighbors). Assume the virtual elements beyond the ends are +∞. Provide the algorithm and analyze its time complexity.

https://leetcode.com/problems/binary-tree-right-side-view/description/

PracHub · Accepted Answer

from typing import List, Optional, Any
from collections import deque

class TreeNode:
    __slots__ = ("val", "left", "right")
    def __init__(self, val: int, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(level: List[Optional[int]]) -> Optional[TreeNode]:
    """Builds a binary tree from level-order array with None as null."""
    if not level:
        return None
    it = iter(level)
    root_val = next(it)
    if root_val is None:
        return None
    root = TreeNode(root_val)
    q = deque([root])
    while q:
        node = q.popleft()
        try:
            lv = next(it)
        except StopIteration:
            break
        if lv is not None:
            node.left = TreeNode(lv)
            q.append(node.left)
        try:
            rv = next(it)
        except StopIteration:
            break
        if rv is not None:
            node.right = TreeNode(rv)
            q.append(node.right)
    return root

def right_side_view(root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
    res: List[int] = []
    q = deque([root])
    while q:
        size = len(q)
        for i in range(size):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
            if i == size - 1:
                res.append(node.val)
    return res

def find_local_min_index(nums: List[int]) -> int:
    """Binary search for any local minimum index with virtual +∞ boundaries."""
    n = len(nums)
    l, r = 0, n - 1
    while l < r:
        m = (l + r) // 2
        if nums[m] > nums[m + 1]:
            l = m + 1
        else:
            r = m
    return l

def right_view_and_local_min(tree: List[Optional[int]], nums: List[int]) -> List[Any]:
    root = build_tree(tree)
    rv = right_side_view(root)
    idx = find_local_min_index(nums)
    return [rv, idx]

Convert the level-order array (with nulls) into a binary tree by iterating the list and linking children in breadth-first order. To compute the right side view, perform a level-order traversal (BFS) and record the last node value in each level. For the local minimum, use a binary search on the array's slope: if nums[mid] > nums[mid+1], a local minimum exists in the right half; otherwise, it exists in the left half (including mid). Distinct values and virtual +∞ on both ends ensure the existence of a local minimum and correctness of the binary search.

Quick Overview

Explanation

Hints

Quick Overview