# Boundary of Binary Tree

• The first algorithm will not work for [1, null, 2, 3, 4] as this algorithm will include 2 element in both left traversal as well as right traversal. Or I am missing something?

• No, 2 will be included only in the right boundary.

• Pls check out my recursive solution. It does this in one iteration.
https://discuss.leetcode.com/topic/87069/java-recursive-solution-beats-94

• Please explain why the output of this test case:
[1,2,null,3,4,null,null,5,6,null,null,null,null]
is [1,2,3,5,6] not [1,2,3,5,6,4]?

[4] is not on the right boundary?

• @tyuan73 root node doesn't have a right child, then according to the definition of right boundary only root node will be considered in right node. Hence 4 should not be there.

• Small typo in "The current node is a root node: In this case, the right child will always be a left boundary node. e.g. relationship between A & C in the above figure."
It should say "The current node is a root node: In this case, the right child will always be a RIGHT boundary node. e.g. relationship between A & C in the above figure."

• Just making "Approach #2 Using PreOrder Traversal" a bit simple as below (accepted):

``````public class Solution {
enum Flag {ROOT, LEFT, RIGHT, MIDDLE};
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> leftBoundary = new ArrayList<>();
List<Integer> leaves = new ArrayList<>();
List<Integer> rightBoundary = new ArrayList<>();
preOrder(root, leftBoundary, leaves, rightBoundary, Flag.ROOT);

return leftBoundary;
}

// root -> left -> right
private void preOrder(TreeNode root, List<Integer> leftBoundary, List<Integer> leaves, List<Integer> rightBoundary, Flag flag) {
if (root == null) {
return;
}
//Root
if (flag == Flag.ROOT || flag == Flag.LEFT) {
} else if (flag == Flag.RIGHT) {
} else if (root.left == null && root.right == null) {
}

//Left
if (root.left != null) {
preOrder(root.left, leftBoundary, leaves, rightBoundary, childFlag(root, flag, true));
}

//Right
if (root.right != null) {
preOrder(root.right, leftBoundary, leaves, rightBoundary, childFlag(root, flag, false));
}
}

private Flag childFlag(TreeNode parent, Flag flag, boolean isLeftChild) {
if (flag == Flag.ROOT) {
return isLeftChild ? Flag.LEFT : Flag.RIGHT;
}

//Parent on left boundary, if exist left child, the right child should be a middle node
if (flag == Flag.LEFT && !isLeftChild && parent.left != null) {
return Flag.MIDDLE;
}

//Parent on right boundary, if exist right node, the left child should be a middle node.
if (flag == Flag.RIGHT && isLeftChild && parent.right != null) {
return Flag.MIDDLE;
}

return flag;
}
}
``````

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