# Boundary of Binary Tree

MEDIUM

A binary tree boundary is the set of nodes (no duplicates) denoting the union of the left boundaryleaves, and right boundary.

The left boundary is the set of nodes on the path from the root to the left-most node. The right boundary is the set of nodes on the path from the root to the right-most node. The left-most node is the leaf node you reach when you always travel to the left subtree if it exists and the right subtree if it doesn’t. The right-most node is defined in the same way except with left and right exchanged. Note that the root may be the left-most and/or right-most node.

Given the `root` of a binary tree, return the values of its boundary in a counter-clockwise direction starting from the `root`.

```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 are node 1,2,4. (4 is the left-most node according to definition)
The left boundary is nodes [1,2,4].
The right boundary is nodes [1,3,6,10].
The leaves are nodes [4,7,8,9,10].
Unioning the sets together gives [1,2,3,4,6,7,8,9,10], which is [1,2,4,7,8,9,10,6,3] in counter-clockwise order.```

Constraints:

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

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) {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
if(!isLeaf(root)){
}
TreeNode p = root.left;
while( p != null){
if(!isLeaf(p)){
}
if(p.left != null){
p = p.left;
}else{
p = p.right;
}
}
Stack<Integer> stack = new Stack<>();
p = root.right;
while( p != null){
if(!isLeaf(p)){
stack.push(p.val);
}
if(p.right != null){
p = p.right;
}else{
p = p.left;
}
}
while(!stack.isEmpty()){
}
return result;
}

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

private void addLeaves(TreeNode node, List<Integer> result){
if(isLeaf(node)){
}
if(node.left != null){
}
if(node.right != null){
• Time complexity : `O(n)` One complete traversal for leaves and two traversals upto depth of binary tree for left and right boundary.
• Space complexity : `O(n)` resres and stack is used.