1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    // Collects the values of all nodes located at the target level.
18    // Because we traverse using in-order (left -> node -> right),
19    // the values are appended in left-to-right order for that level.
20    private List<Integer> levelValues = new ArrayList<>();
21
22    // The target depth whose median value we want to return.
23    private int targetLevel;
24
25    /**
26     * Returns the median value among all nodes located at the given level.
27     *
28     * @param root  the root of the binary tree
29     * @param level the target level (root is at level 0)
30     * @return the median value at the target level, or -1 if no node exists there
31     */
32    public int levelMedian(TreeNode root, int level) {
33        this.targetLevel = level;
34        // Traverse the tree starting from depth 0.
35        dfs(root, 0);
36        // If no node was found at the target level, return -1.
37        // Otherwise return the middle element (left-to-right ordered).
38        return levelValues.isEmpty() ? -1 : levelValues.get(levelValues.size() / 2);
39    }
40
41    /**
42     * Performs an in-order depth-first search to gather node values at the target level.
43     *
44     * @param node  the current node being visited
45     * @param depth the depth of the current node (root is at depth 0)
46     */
47    private void dfs(TreeNode node, int depth) {
48        // Base case: reached a null child, nothing to process.
49        if (node == null) {
50            return;
51        }
52        // Visit the left subtree first so values are collected left-to-right.
53        dfs(node.left, depth + 1);
54        // If the current node sits exactly at the target level, record its value.
55        if (depth == targetLevel) {
56            levelValues.add(node.val);
57        }
58        // Then visit the right subtree.
59        dfs(node.right, depth + 1);
60    }
61}
62

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    int levelMedian(TreeNode* root, int level) {
15        // Collect all node values located at the target level.
16        // Because we traverse in-order (left -> node -> right),
17        // the values are gathered in ascending order of their horizontal position,
18        // which conveniently mirrors the left-to-right order on that level.
19        std::vector<int> values;
20
21        // Recursive lambda performing a depth-first, in-order traversal.
22        // 'node' is the current node, 'depth' is its distance from the root.
23        auto dfs = [&](this auto&& dfs, TreeNode* node, int depth) -> void {
24            // Base case: a null node contributes nothing.
25            if (node == nullptr) {
26                return;
27            }
28
29            // Visit the left subtree first.
30            dfs(node->left, depth + 1);
31
32            // If the current node sits on the requested level, record its value.
33            if (depth == level) {
34                values.push_back(node->val);
35            }
36
37            // Finally visit the right subtree.
38            dfs(node->right, depth + 1);
39        };
40
41        // Kick off the traversal from the root at depth 0.
42        dfs(root, 0);
43
44        // If no node exists on the target level, return -1 as a sentinel.
45        // Otherwise, return the middle element (upper-median for even counts).
46        return values.empty() ? -1 : values[values.size() / 2];
47    }
48};
49

1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 *     val: number
5 *     left: TreeNode | null
6 *     right: TreeNode | null
7 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 *         this.val = (val===undefined ? 0 : val)
9 *         this.left = (left===undefined ? null : left)
10 *         this.right = (right===undefined ? null : right)
11 *     }
12 * }
13 */
14function levelMedian(root: TreeNode | null, level: number): number {
15    // Stores the values of all nodes found at the target level,
16    // collected in left-to-right order due to the traversal scheme.
17    const values: number[] = [];
18
19    /**
20     * Depth-first traversal in the order: left subtree -> current node -> right subtree.
21     * @param node  The current node being visited.
22     * @param depth The depth of the current node (root starts at 0).
23     */
24    const dfs = (node: TreeNode | null, depth: number): void => {
25        // Base case: nothing to do for a null node.
26        if (node === null) {
27            return;
28        }
29
30        // Traverse the left subtree first.
31        dfs(node.left, depth + 1);
32
33        // Record the value only when the current depth matches the target level.
34        if (depth === level) {
35            values.push(node.val);
36        }
37
38        // Traverse the right subtree last.
39        dfs(node.right, depth + 1);
40    };
41
42    // Kick off the traversal from the root at depth 0.
43    dfs(root, 0);
44
45    // If no node exists at the target level, return -1 as a sentinel value.
46    if (values.length === 0) {
47        return -1;
48    }
49
50    // Return the middle element (by collection index) at that level.
51    // `values.length >> 1` is an integer division by 2.
52    return values[values.length >> 1];
53}
54