Boundary traversal of binary tree in java

ghz 10months ago ⋅ 147 views

Boundary traversal of a binary tree involves traversing the boundary nodes of the tree in a specific order: left boundary (excluding leaves), leaf nodes (from left to right), and right boundary (excluding leaves). Here's how you can implement boundary traversal of a binary tree in Java:

class TreeNode {
    int val;
    TreeNode left, right;

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

public class BoundaryTraversalBinaryTree {
    public void printBoundary(TreeNode root) {
        if (root == null) return;

        System.out.print(root.val + " "); // Print root

        printLeftBoundary(root.left); // Print left boundary
        printLeaves(root.left); // Print left leaves
        printLeaves(root.right); // Print right leaves
        printRightBoundary(root.right); // Print right boundary
    }

    private void printLeftBoundary(TreeNode node) {
        if (node == null || (node.left == null && node.right == null)) return;

        System.out.print(node.val + " ");
        if (node.left != null) printLeftBoundary(node.left);
        else printLeftBoundary(node.right);
    }

    private void printRightBoundary(TreeNode node) {
        if (node == null || (node.left == null && node.right == null)) return;

        if (node.right != null) printRightBoundary(node.right);
        else printRightBoundary(node.left);
        System.out.print(node.val + " ");
    }

    private void printLeaves(TreeNode node) {
        if (node == null) return;

        if (node.left == null && node.right == null) {
            System.out.print(node.val + " ");
            return;
        }
        printLeaves(node.left);
        printLeaves(node.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(20);
        root.left = new TreeNode(8);
        root.right = new TreeNode(22);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(12);
        root.left.right.left = new TreeNode(10);
        root.left.right.right = new TreeNode(14);
        root.right.right = new TreeNode(25);

        BoundaryTraversalBinaryTree boundaryTraversal = new BoundaryTraversalBinaryTree();
        boundaryTraversal.printBoundary(root);
    }
}

In this implementation:

  • The printBoundary method takes the root of the binary tree and prints its boundary nodes in the required order.
  • Three helper methods (printLeftBoundary, printRightBoundary, and printLeaves) are used to print the left boundary, right boundary, and leaf nodes respectively.
  • The main method creates a sample binary tree, and the printBoundary method is called with the root node to print its boundary nodes.
#algorithm