Boundary Order Traversal

Problem Statement:

You are given a binary tree having ‘n’ nodes. The boundary nodes of a binary tree include the nodes from the left and right boundaries and the leaf nodes, each node considered once. Figure out the boundary nodes of this binary tree in an Anti-Clockwise direction starting from the root node.

Example : Input: Consider the binary tree A as shown in the figure:

Output: [10, 5, 3, 7, 18, 25, 20] Explanation: As shown in the figure The nodes on the left boundary are [10, 5, 3] The nodes on the right boundary are [10, 20, 25] The leaf nodes are [3, 7, 18, 25].

Please note that nodes 3 and 25 appear in two places but are considered once.

Solution:

class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> boundary = new ArrayList<>();
        if (root == null) {
            return boundary;
        }
        
        boundary.add(root.val);
        
        leftBoundary(root.left, boundary);
        leaves(root.left, boundary);
        leaves(root.right, boundary);
        rightBoundary(root.right, boundary);
        
        return boundary;
    }
    
    private void leftBoundary(TreeNode node, List<Integer> boundary) {
        if (node == null || (node.left == null && node.right == null)) {
            return;
        }
        
        boundary.add(node.val);
        
        if (node.left != null) {
            leftBoundary(node.left, boundary);
        } else {
            leftBoundary(node.right, boundary);
        }
    }
    
    private void leaves(TreeNode node, List<Integer> boundary) {
        if (node == null) {
            return;
        }
        
        if (node.left == null && node.right == null) {
            boundary.add(node.val);
            return;
        }
        
        leaves(node.left, boundary);
        leaves(node.right, boundary);
    }
    
    private void rightBoundary(TreeNode node, List<Integer> boundary) {
        if (node == null || (node.left == null && node.right == null)) {
            return;
        }
        
        if (node.right != null) {
            rightBoundary(node.right, boundary);
        } else {
            rightBoundary(node.left, boundary);
        }
        
        boundary.add(node.val);
    }
}