# 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
```java
/**
* 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 boundaryOfBinaryTree(TreeNode root) {
// TC: O(N), N->Number of nodes
// SC: Auxillary space complexity
List 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 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 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 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 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);
}
}
```
