# Java(12ms) - left boundary, left leaves, right leaves, right boundary

• ``````List<Integer> nodes = new ArrayList<>(1000);
public List<Integer> boundaryOfBinaryTree(TreeNode root) {

if(root == null) return nodes;

leftBoundary(root.left);
leaves(root.left);
leaves(root.right);
rightBoundary(root.right);

return nodes;
}
public void leftBoundary(TreeNode root) {
if(root == null || (root.left == null && root.right == null)) return;
if(root.left == null) leftBoundary(root.right);
else leftBoundary(root.left);
}
public void rightBoundary(TreeNode root) {
if(root == null || (root.right == null && root.left == null)) return;
if(root.right == null)rightBoundary(root.left);
else rightBoundary(root.right);
}
public void leaves(TreeNode root) {
if(root == null) return;
if(root.left == null && root.right == null) {
return;
}
leaves(root.left);
leaves(root.right);
}``````

• wow~ brilliant to use

``````    leaves(root.left);
leaves(root.right);
``````

I tried similar idea to use leaves(root) and then remove the duplicate node with left and right boundary, but there are several corner cases hard to deal with.

• The idea is brilliant and the structure is crystal clear, this is what solution you may come up with during an interview!

• Nice solution! Please check-out my recursive Java solution which takes 11ms and beats 94% Java Solutions.

``````public class Solution {
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
List<Integer> ls = new ArrayList<Integer>();
if(root!=null){
lookupElems(root.left,ls,true,false);
lookupElems(root.right,ls,false,true);
}
return ls;
}

private void lookupElems(TreeNode root,List<Integer> ls,boolean isLeftBoundary,boolean isRightBoundary){
if (root==null) {
return;
}
if (root.left==null && root.right==null) {
return;
}
if (isLeftBoundary) {
}
lookupElems(root.left,ls,root.left!=null && isLeftBoundary,root.right==null && isRightBoundary);
lookupElems(root.right,ls,root.left==null && isLeftBoundary,root.right!=null && isRightBoundary);
if (isRightBoundary) {
}
}
}
``````

Step by step approach here - https://discuss.leetcode.com/topic/87069/java-recursive-solution-beats-94

• Nice solution. Very easy to understand and flow is elegant. There is another solution that can traverse the tree only once.

• @jaqenhgar
Please check this input: [1,2,3,null, null, 4, null, 5, 8, 6,7,null,9]
Your output is [1,2,6,7,9,8,4,3]. However, this is the not the boundary of the tree.
The right one should be [1,2,5,6,7,9,8,4,3] or [1,2,4,5,6,7,9,8,3].

The definition of the boundary by OJ is incorrect here.

• Hi @ganesh9 I have almost the same solution as yours~

• Slightly modified version which eliminates the 2 calls to leaves(root). I did not find that necessary.

List<Integer> nodes = new ArrayList<>(1000);
public List<Integer> boundaryOfBinaryTree(TreeNode root) {

``````if(root == null) return nodes;
if (root.left != null || root.right != null)

leftBoundary(root.left);
leaves(root);
rightBoundary(root.right);

return nodes;
``````

}

• Do anybody know why my output for this case wrong? Why the OJ output here can contains duplicate? Isn't the question requires no duplicate?

• @ctfu I have figured out myself.
What the question mean by no duplicate it actually means there is no duplicate inclusion of the connecting elements between boundaries. I don't know if is just me, but the question's definition about no duplicates does throw me off.

• This post is deleted!

• This post is deleted!

• if(root == null || (root.left == null && root.right == null)) return;
This condition is very smart. Avoid adding leftmost leaf node and rightmost leaf node while traverse left and right boundary.

• This post is deleted!

• @ctfu the problem says no duplicate nodes, not no duplicate values.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.