Boundary of Binary Tree

Problem Statement

In computational tree structures, the boundary of a binary tree encapsulates its edges when envisioned from a top view, encompassing the root, the left boundary, the leaf nodes in a sequential left-to-right manner, and the reverse order of the right boundary. Here's a detailed breakdown:

• Left Boundary: This starts from the root's left child (if it exists) and follows through the outer left nodes until the last non-leaf node. If a node has no left child but has a right child, then the right child is considered part of the left boundary. The terminus of this boundary is marked by a non-leaf node or when no further children exist.

• Right Boundary: Mirroring the left, this boundary begins from the root's right child (if present) and continues through the outer right nodes till the end, omitting the last leaf node.

• Leaves: These are the nodes devoid of any children and are not considered either the starting or terminal nodes of the tree, except for being part of their respective boundaries if they fall into the definitions above.

The task is to iteratively concatenate the values of the root, left boundary, leaves in sequential order, and the reverse of the right boundary to form the full boundary representation of the binary tree.

Examples

Example 1

Input:

root = [1,null,2,3,4]

Output:

[1,3,4,2]
**Explanation:**
- The left boundary is empty because the root does not have a left child.
- The right boundary follows the path starting from the root's right child 2 -> 4.
4 is a leaf, so the right boundary is [2].
- The leaves from left to right are [3,4].
Concatenating everything results in [1] + [] + [3,4] + [2] = [1,3,4,2].

Example 2

Input:

root = [1,2,3,4,5,6,null,null,null,7,8,9,10]

Output:

[1,2,4,7,8,9,10,6,3]
**Explanation:**
- The left boundary follows the path starting from the root's left child 2 -> 4.
4 is a leaf, so the left boundary is [2].
- The right boundary follows the path starting from the root's right child 3 -> 6 -> 10.
10 is a leaf, so the right boundary is [3,6], and in reverse order is [6,3].
- The leaves from left to right are [4,7,8,9,10].
Concatenating everything results in [1] + [2] + [4,7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3].

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -1000 <= Node.val <= 1000

Approach and Intuition

When tackling the problem of determining the boundary of a binary tree, the solution leverages a systematic approach to traverse different parts of the tree:

1. Root Identification: The root is a straightforward add since it's guaranteed to be the first in the boundary.

2. Construction of the Left Boundary:

   • Start at the root’s left child and consider moving down to either the left or right child, prioritizing left.
   • Continue this until you reach a node which is either a leaf or has no children to move further down non-leaf nodes.

3. Identification and Collection of Leaves:

   • Utilize an in-order traversal (left-root-right) to ensure leaves are collected from left to right, for both the left subtree and the right subtree of the root.

4. Construction of the Right Boundary:

   • Similar to the left boundary but instead, start from the root's right child.
   • Continue down prioritizing the right child over the left, until there are no non-leaf nodes left.
   • Reverse the collected nodes as they should be added last and in reverse order to the boundary.

Steps of Execution in Examples:

• For Example 1:

  • As the root has no left child, the left boundary is empty.
  • The right boundary is captured by following from the root’s right child down to node 4, which is a leaf and hence not included.
  • Traversing from left to right, the leaves collected are [3,4].
  • Concatenating these parts together gives [1,3,4,2].

• For Example 2:

  • The path for the left boundary goes from root's left child down to node 4, which is omitted as it's at its leaf stage.
  • The right boundary path capturing stops at node 10.
  • The leaves are collected in their in-order appearance [4,7,8,9,10].
  • Combining all these findings results in [1,2,4,7,8,9,10,6,3] as the boundary value list.

The above approach ensures a continuous, linear-time traversal across various segments of the binary tree, efficiently piecing together its boundary representation.

Solutions

/**
 * Class for operating on binary tree
 */
public class BinaryTreeBoundaries {
    public List<Integer> getBoundary(TreeNode node) {
        List<Integer> leftSide = new LinkedList<>(), rightSide = new LinkedList<>(), bottomLeaves = new LinkedList<>();
        traversePreorder(node, leftSide, rightSide, bottomLeaves, 0);
        leftSide.addAll(bottomLeaves);
        leftSide.addAll(rightSide);
        return leftSide;
    }

    public boolean isLeafNode(TreeNode n) {
        return (n.left == null && n.right == null);
    }

    public boolean isRightEdge(int mark) {
        return (mark == 2);
    }

    public boolean isLeftEdge(int mark) {
        return (mark == 1);
    }

    public boolean isRootNode(int mark) {
        return (mark == 0);
    }

    public int flagForLeftChild(TreeNode n, int mark) {
        if (isLeftEdge(mark) || isRootNode(mark))
            return 1;
        else if (isRightEdge(mark) && n.right == null)
            return 2;
        else return 3;
    }

    public int flagForRightChild(TreeNode n, int mark) {
        if (isRightEdge(mark) || isRootNode(mark))
            return 2;
        else if (isLeftEdge(mark) && n.left == null)
            return 1;
        else return 3;
    }
    
    public void traversePreorder(TreeNode n, List<Integer> leftSide, List<Integer> rightSide, List<Integer> bottomLeaves, int mark) {
        if (n == null)
            return;
        if (isRightEdge(mark))
            rightSide.add(0, n.val);
        else if (isLeftEdge(mark) || isRootNode(mark))
            leftSide.add(n.val);
        else if (isLeafNode(n))
            bottomLeaves.add(n.val);
        traversePreorder(n.left, leftSide, rightSide, bottomLeaves, flagForLeftChild(n, mark));
        traversePreorder(n.right, leftSide, rightSide, bottomLeaves, flagForRightChild(n, mark));
    }
}