Boundary Traversal of Binary Tree

Problem Statment

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. (link)

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.

Detailed explanation ( Input/output format, Notes, Images )

Sample Input 1:

10 5 20 3 8 18 25 -1 -1 7 -1 -1 -1 -1 -1 -1 -1

Sample Output 1:

10 5 3 7 18 25 20

Explanation of Sample Input 1:

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.

Sample Input 2:

100 50 150 25 75 140 200 -1 30 70 80 -1 -1 -1 -1 -1 35 -1 -1 -1 -1 -1 -1

Sample Output 2:

100 50 25 30 35 70 80 140 200 150

Constraints:

1 <= n <= 10000

Where 'n' is the total number of nodes in the binary tree.

Time Limit: 1 sec

Solution

We can break the problem into 3 sections and add them to the answer list.

• Traverse on the left end of the binary tree until the leaf node.

• Gather all the leaf nodes.

• Traverse on the right end of the binary tree until the leaf node. (Add these in reverse order to the answer list)

Time: O(H) + O(H) + O(N)
Space: O(N)

Reasoning: Traversing the left or right branch will take time proportional to the height of the tree. However, collecting the leaf nodes requires traversing all the nodes.

public class Solution {

    private static void addLeftBoundaryNodes(TreeNode root, List<Integer> ans){
        if(root == null || isLeaf(root)) return;

        ans.add(root.data);
        if(root.left!=null){
            addLeftBoundaryNodes(root.left, ans);
        }
        else{
            addLeftBoundaryNodes(root.right, ans);
        }
    }

    private static void addLeafNodes(TreeNode root, List<Integer> ans){
        if(isLeaf(root)){
            ans.add(root.data);
            return;
        }
        if(root.left!=null) addLeafNodes(root.left, ans);
        if(root.right!=null) addLeafNodes(root.right, ans);
    }

    private static void addRightBoundaryNodes(TreeNode root, List<Integer> ans, int startIndex){
        if(root == null || isLeaf(root)) return;

        ans.add(startIndex, root.data);

        if(root.right!=null){
            addRightBoundaryNodes(root.right, ans, startIndex);
        }
        else{
            addRightBoundaryNodes(root.left, ans, startIndex);
        }
    }

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

    public static List<Integer> traverseBoundary(TreeNode root){
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;
        ans.add(root.data);
        addLeftBoundaryNodes(root.left, ans);
        addLeafNodes(root, ans);
        int startIndex = ans.size();
        addRightBoundaryNodes(root.right, ans, startIndex);
        return ans;
    }
}