Print or return nodes between two given levels in a binary tree

Problem

Given a binary tree and two levels (low and high), print all the nodes present in the binary tree between those levels inclusively. The levels are specified starting from level 0 (root level) to level n. Nodes at each level are printed in level order.

Examples

Example 1

graph TD;
	subgraph l0["Level 0"]
		A("1")
	end
	subgraph l1["Level 1"]
		B("2")
		C("3")
	end
	subgraph l2["Level 2"]
		D("4")
		E("5")
		F("6")
		G("7")
	end
	
	A --- B & C
	B --- D & E
	C --- F & G

 Input:
 Binary Tree:
         1
       /   \
      2     3
     / \   / \
    4   5 6   7
 low = 1
 high = 2
 
 Output:
 2 3 4 5 6 7
 
 Explanation:
 Nodes at level 1 are [2, 3]. Nodes at level 2 are [4, 5, 6, 7]. These nodes are between levels 1 and 2 inclusively.

Example 2

 Input:
 Binary Tree:
         1
        /
       2
      / \
     3   4
    /
   5
 low = 2
 high = 3
 
 Output:
 3 4 5
 
 Explanation:
 Nodes at level 2 are [3, 4]. Nodes at level 3 are [5]. These nodes are between levels 2 and 3 inclusively.

Solution

Method 1 - Level order traversal

Intuition

1. Tree Traversal: Use breadth-first search (BFS) for level-order traversal as it naturally processes nodes level by level.
2. Node Filtering: During traversal, keep track of the current level. If the current level falls between the provided low and high bounds, add the nodes of that level to the result.
3. Control Bounds: Stop processing nodes once the traversal reaches a level higher than high.

Approach

1. Start with the root node and perform level-order traversal using a queue.
2. Store nodes for each level in the queue while keeping track of the current level.
3. For each level, check if it falls between the bounds low and high. If yes, include its nodes in the output.
4. Continue the traversal until no nodes remain or the level exceeds high.

Code

Java

class Solution {
    public List<Integer> printNodesBetweenLevels(TreeNode root, int low, int high) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            if (level >= low && level <= high) {
                result.addAll(currentLevel);
            }

            level++;
            if (level > high) {
                break;
            }
        }
        return result;
    }

    // Example usage
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        Solution solution = new Solution();
        System.out.println(solution.printNodesBetweenLevels(root, 1, 2)); // Output: [2, 3, 4, 5, 6, 7]
    }
}

Python

class Solution:
    def printNodesBetweenLevels(self, root, low, high):
        if not root:
            return []

        result = []
        queue = deque([root])
        level = 0

        while queue:
            size = len(queue)
            current_level = []

            for _ in range(size):
                node = queue.popleft()
                current_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            if low <= level <= high:
                result.extend(current_level)

            level += 1
            if level > high:
                break

        return result


# Example usage
if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(7)

    solution = Solution()
    print(solution.printNodesBetweenLevels(root, 1, 2))  # Output: [2, 3, 4, 5, 6, 7]

Complexity

• ⏰ Time complexity: O(n). The algorithm visits every node in the binary tree once during the breadth-first traversal.
• 🧺 Space complexity: O(w). The space required is proportional to the maximum width w of the tree (the largest number of nodes at any level).