Tree Misc

Boundary of Binary Tree

we need to distinguish the left and right subtree. The total time complexity is O(n) because four basic operations are all O(n) time complexity.

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

    if(root == null) return nodes;

    nodes.add(root.val);
    leftBoundary(root.left);  // O(n)
    leaves(root.left);       // O(n)
    leaves(root.right);      // O(n)
    rightBoundary(root.right);  // O(n)

    return nodes;
}
public void leftBoundary(TreeNode root) {
    if(root == null || (root.left == null && root.right == null)) return;
    nodes.add(root.val);
    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);
    nodes.add(root.val); // add after child visit(reverse)
}
public void leaves(TreeNode root) {
    if(root == null) return;
    if(root.left == null && root.right == null) {
        nodes.add(root.val);
        return;
    }
    leaves(root.left);
    leaves(root.right);
}