Get Level of A Node in Binary Tree in Java

ghz 10months ago ⋅ 261 views

1. Overview

In this solution, we'll discuss how to find the level of a given node in a binary tree in Java. We'll explore both recursive and iterative approaches to solve this problem.

2. Introduction to Problem Statement

Given a binary tree and a target node, we need to find the level of the target node in the binary tree.

3. Implementation

3.1 Recursive

The recursive approach involves traversing the binary tree recursively until we find the target node. We'll maintain a level variable that keeps track of the current level during traversal.

class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public class BinaryTree {
    public int findLevelRecursive(TreeNode root, int target, int level) {
        // Base case: If the root is null, return 0
        if (root == null) {
            return 0;
        }
        
        // If the root's value matches the target, return the current level
        if (root.val == target) {
            return level;
        }
        
        // Recursively search in the left and right subtrees
        int leftLevel = findLevelRecursive(root.left, target, level + 1);
        if (leftLevel != 0) {
            return leftLevel;
        }
        return findLevelRecursive(root.right, target, level + 1);
    }

    public static void main(String[] args) {
        // Create a binary tree
        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);

        int target = 5;
        BinaryTree bt = new BinaryTree();
        int level = bt.findLevelRecursive(root, target, 1);
        System.out.println("Level of node " + target + " is: " + level);
    }
}

3.2 Iterative

The iterative approach uses level-order traversal (BFS) to find the level of the target node in the binary tree.

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public class BinaryTree {
    public int findLevelIterative(TreeNode root, int target) {
        if (root == null) {
            return 0;
        }

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

        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;

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

    public static void main(String[] args) {
        // Create a binary tree
        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);

        int target = 5;
        BinaryTree bt = new BinaryTree();
        int level = bt.findLevelIterative(root, target);
        System.out.println("Level of node " + target + " is: " + level);
    }
}

4. Complete Java Program

The complete Java program includes both recursive and iterative solutions to find the level of a given node in a binary tree.

5. Conclusion

In this solution, we discussed how to find the level of a given node in a binary tree using both recursive and iterative approaches. These approaches provide different ways to solve the problem based on the requirements and constraints of the application.

#algorithm