How to Print Leaf Nodes of a Binary Tree in Java

ghz 10months ago ⋅ 84 views

1. Introduction

In a binary tree, leaf nodes are nodes with no children (both left and right child are null). Printing the leaf nodes of a binary tree involves traversing the tree and printing the values of all leaf nodes.

2. What are Leaf Nodes?

Leaf nodes are the nodes in a binary tree that do not have any child nodes.

3. Implementation

3.1 Recursive Solution

In the recursive solution, we traverse the tree recursively and print the values of leaf nodes.

3.2 Iterative Solution

In the iterative solution, we use a stack or queue to traverse the tree iteratively and print the values of leaf nodes.

4. Recursive Solution

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

public class PrintLeafNodes {
    public static void main(String[] args) {
        // Example 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);
        
        System.out.println("Leaf nodes (Recursive):");
        printLeafNodesRecursive(root);
    }
    
    public static void printLeafNodesRecursive(TreeNode root) {
        if (root == null) return;
        
        if (root.left == null && root.right == null) {
            System.out.print(root.val + " ");
        }
        
        printLeafNodesRecursive(root.left);
        printLeafNodesRecursive(root.right);
    }
}

5. Iterative Solution

import java.util.*;

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

public class PrintLeafNodes {
    public static void main(String[] args) {
        // Example 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);
        
        System.out.println("Leaf nodes (Iterative):");
        printLeafNodesIterative(root);
    }
    
    public static void printLeafNodesIterative(TreeNode root) {
        if (root == null) return;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            
            if (node.left == null && node.right == null) {
                System.out.print(node.val + " ");
            }
            
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }
}

6. Complete Java Program

This program prints the leaf nodes of a binary tree using both recursive and iterative methods.

7. Conclusion

Printing the leaf nodes of a binary tree is a common operation, and it can be efficiently implemented using both recursive and iterative approaches. Depending on the requirements and constraints, either approach can be chosen for implementation.

#algorithm