Boundary of binary tree

XXX. Boundary of Binary Tree

Tree

DFS

Problem Statement:

Given a binary tree, return the boundary of the tree in an anti-clockwise direction. The boundary includes:

• The root node (if not null).
• The left boundary nodes (excluding leaf nodes and the root).
• All leaf nodes (from left to right).
• The right boundary nodes (excluding leaf nodes and the root, added in reverse order).

Algorithm:

1. If the tree is empty, return an empty list.
2. Add the root node to the boundary.
3. Traverse the left boundary using a recursive helper function:
   • Add nodes that are not leaves.
   • Recurse on the left child if it exists; otherwise, recurse on the right child.
4. Traverse all leaf nodes using another helper function:
   • Perform a DFS to find all leaf nodes.
   • Add the value of each leaf node to the result.
5. Traverse the right boundary using a recursive helper function:
   • Add nodes that are not leaves, but in reverse order (post-order).
   • Recurse on the right child if it exists; otherwise, recurse on the left child.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to recursion stack space.

Java Implementation:

class Solution {

    List nodes = new ArrayList<>();

    public List boundaryOfBinaryTree(TreeNode root) {
        if (root == null) return nodes;

        // Add the root node if it exists
        nodes.add(root.val);

        // Process the left boundary (excluding leaves)
        leftBoundary(root.left);

        // Add all leaf nodes (from left to right)
        leaves(root.left);
        leaves(root.right);

        // Process the right boundary (excluding leaves, in reverse order)
        rightBoundary(root.right);

        return nodes;
    }

    // Traverse the left boundary
    public void leftBoundary(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return;

        nodes.add(root.val); // Add the current node
        if (root.left != null) 
            leftBoundary(root.left); // Prefer left child
        else 
            leftBoundary(root.right); // If no left child, go to right child
    }

    // Traverse the right boundary in reverse order
    public void rightBoundary(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return;

        if (root.right != null) 
            rightBoundary(root.right); // Prefer right child
        else 
            rightBoundary(root.left); // If no right child, go to left child

        nodes.add(root.val); // Add the node after recursion for reverse order
    }

    // Add all leaf nodes
    public void leaves(TreeNode root) {
        if (root == null) return;

        // If it's a leaf node, add it to the list
        if (root.left == null && root.right == null) {
            nodes.add(root.val);
            return;
        }

        // Recur for left and right children
        leaves(root.left);
        leaves(root.right);
    }
}