Dsa
Trees
Medium
The Shadow of the World Tree
A binary tree is grown on a 2D plane. The root is at (0, 0). For any node at (x, y), its left child is at (x-1, y-1) and its right child is at (x+1, y-1). A node is 'visible' from the sky if no other node exists at the same x-coordinate with a higher y-coordinate. Given the tree structure, calculate the total number of visible nodes.
Input Format:
Line 1: N (number of nodes)
Next N lines: id left_child right_child (-1 if no child)
Nodes are 0 to N-1. The root is 0.
Example:
Input:
3
0 1 2
1 -1 -1
2 -1 -1
Output:
3
Key concepts
binary treevertical order traversalcoordinate mapping
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now