TODO: 545. Boundary of Binary Tree

Problem

Intuition

Time Complexity

O(N)

In worst case, we might need to explore all the nodes

Space Complexity

O(1)

Auxiliary space complexity

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        // TC: O(N), N->Number of nodes
        // SC: Auxillary space complexity
        List<Integer> result = new ArrayList<>();

        if(root == null) {
            return result;
        }

        // Add this condition to add root value, incase of single node tree,
        // this condition is failed and is caught in addLeaves
        if(!isLeaf(root)) {
            result.add(root.val);
        }

        // According to the boundary definition, left + leaves + right
        addLeftBoundary(root, result);
        addLeaves(root, result);
        addRightBoundary(root, result);

        return result;
    }

    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }

    private void addLeftBoundary(TreeNode root, List<Integer> result) {
        TreeNode node = root.left;
        
        // Explore left most nodes in left subtree from root
        while(node != null) {
            // Add the values only if it is not a leaf node
            if(!isLeaf(node)) result.add(node.val);

            // Explore towards left 
            if(node.left != null) node = node.left;
            else node = node.right; // In case if left does not exit, explore right
        }
    }

    private void addLeaves(TreeNode node, List<Integer> result) {
        if(node == null) return;
        
        // This can be acheived by any DFS, Used pre order here
        // with condition that node should be leaf
        if(isLeaf(node)) result.add(node.val);

        if(node.left!=null) addLeaves(node.left, result);
        if(node.right!=null) addLeaves(node.right, result);
    }

    private void addRightBoundary(TreeNode root, List<Integer> result) {
        TreeNode node = root.right;
        // Same as adding left boundary, but since we are moving the border
        // anti-clockwise, reverse the order of insertion using LinkedList
        List<Integer> current = new LinkedList<>();
        
        while(node != null) {
            // Add the values only if it is not a leaf node
            if(!isLeaf(node)) current.addFirst(node.val);

            // Explore towards right
            if(node.right != null) node = node.right;
            else node = node.left; // In case if right does not exit, explore left
        }
        // Add all the linkedlist values to result
        for(int nodeVal: current) result.add(nodeVal);
    }
}