Problem statement

Given the root of a binary tree whose node values are all distinct, and an integer target, return the level of the node whose value is target.

The root is on level 1, its children on level 2, and so on. If no node holds target, return 0.

Example 1

Input: root = [3,2,5,1,4], target = 4
Output: 3
Explanation: 3 is on level 1, 2 and 5 on level 2, and 1 and 4 on level 3.

Example 2

Input: root = [3,2,5,1,4], target = 3
Output: 1
Explanation: The root itself is on level 1.

Example 3

Input: root = [7,null,9,8], target = 10
Output: 0
Explanation: No node holds 10.

Constraints

• 1 <= number of nodes <= 10^5
• 1 <= Node.val <= 10^5
• all node values are distinct
• 1 <= target <= 10^5

Hints for Level of a Node in Binary Tree

1. Hint 1

   A node's level is one more than its parent's.

2. Hint 2

   A breadth-first walk processes the tree one whole level at a time — keep a counter of the level being processed.

3. Hint 3

   Return the counter as soon as a node of the current level holds target; if the walk ends without meeting it, return 0.

How to solve Level of a Node in Binary Tree

Walk the tree level by level with a counter; the counter's value when target turns up is its level.

Approach

1. Start with the level holding only the root and a counter of 1.
2. Scan the current level: if any node holds target, return the counter.
3. Otherwise gather every child into the next level and add 1 to the counter.
4. When no level is left, return 0.

Why it works

The k-th level processed holds exactly the nodes k − 1 edges below the root, so the counter equals the level of every node being scanned. Values are distinct, so the first match is the only one.

Complexity

• Time — O(n)
• Space — O(w), w the largest number of nodes on one level

Pitfalls

• Levels start at 1 for the root here, not 0.
• A depth-first search works too, but carry the depth down with the call rather than counting returns on the way up.

Reference solution

Python

from typing import Optional

def getLevel(root: Optional[TreeNode], target: int) -> int:
    level = [root] if root else []
    depth = 1
    while level:
        nxt = []
        for node in level:
            if node.val == target:
                return depth
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        level = nxt
        depth += 1
    return 0

Java

public static int getLevel(TreeNode root, int target) {
    List<TreeNode> level = new ArrayList<>();
    if (root != null) level.add(root);
    int depth = 1;
    while (!level.isEmpty()) {
        List<TreeNode> next = new ArrayList<>();
        for (TreeNode node : level) {
            if (node.val == target) return depth;
            if (node.left != null) next.add(node.left);
            if (node.right != null) next.add(node.right);
        }
        level = next;
        depth++;
    }
    return 0;
}

C++

int getLevel(TreeNode* root, int target) {
    vector<TreeNode*> level;
    if (root) level.push_back(root);
    int depth = 1;
    while (!level.empty()) {
        vector<TreeNode*> next;
        for (TreeNode* node : level) {
            if (node->val == target) return depth;
            if (node->left) next.push_back(node->left);
            if (node->right) next.push_back(node->right);
        }
        level.swap(next);
        depth++;
    }
    return 0;
}

JavaScript

var getLevel = function(root, target) {
    var level = root === null ? [] : [root], depth = 1;
    while (level.length > 0) {
        var next = [];
        for (var i = 0; i < level.length; i++) {
            var node = level[i];
            if (node.val === target) return depth;
            if (node.left !== null) next.push(node.left);
            if (node.right !== null) next.push(node.right);
        }
        level = next;
        depth++;
    }
    return 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy
• Nodes at Distance K from Root Easy