Rightmost Nodes of a Binary Tree

Finding the visible nodes from the left in a binary tree is a classic tree traversal problem. It tests your ability to navigate tree structures and apply level-order traversal, a crucial skill for many tree-related interview questions.

treebinary treelevel-order traversalbreadth-first searchbfs

Problem Statement

Given the root of a binary tree, imagine standing on the left side of the tree. Return an array containing the values of the nodes that are visible from your vantage point, ordered from top to bottom. A node is visible if no other node on the same level to its left obscures it.

Example 1

Input: A binary tree with root 5, left child 2, right child 9. 2 has left child 1, right child 3. 9 has left child 7, right child 10.

Output: [5, 2, 7]

From the left, we see 5 at the top level. On the second level, 2 is visible. On the third level, 7 is visible because it's the leftmost node.

Example 2

Input: A binary tree with root 1, left child 2, right child 3. 2 has only a right child 5. 3 has left child 6, right child 7. 5 has a left child 8.

Output: [1, 2, 6, 8]

From the left, we see 1 at the top level. On the second level, 2 is visible. On the third level, 6 is visible. On the fourth level, 8 is visible.

Constraints

-The number of nodes in the tree is between 0 and 5000.
-Node values are unique integers.
-Node values range from -1000 to 1000.

Brute Force Approach

The brute force approach would be like trying to find the leftmost house on each street by walking down every possible path from the top of the neighborhood. You'd explore every single route, and at each level, you'd keep track of all the nodes and then pick the leftmost one. This involves exploring all paths, resulting in exponential time complexity.

TimeO(2^n)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem