[Programming Problem] Boundary of Binary Tree

Input:
  1
   \
    2
   / \
  3   4
 
Ouput:
[1, 3, 4, 2]
 
Explanation:
The root doesn't have left subtree, so the root itself is left boundary.
The leaves are node 3 and 4.
The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
So order them in anti-clockwise without duplicates and we have [1,3,4,2].

Input: 1 \ 2 / \ 3 4 Ouput: [1, 3, 4, 2] Explanation: The root doesn't have left subtree, so the root itself is left boundary. The leaves are node 3 and 4. The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary. So order them in anti-clockwise without duplicates and we have [1,3,4,2].

Input:
    ____1_____
   /          \
  2            3
 / \          / 
4   5        6   
   / \      / \
  7   8    9  10  
 
Ouput:
[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 leaves are node 4,7,8,9,10.
The right boundary are node 1,3,6,10. (10 is the right-most node).
So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

Input: ____1_____ / \ 2 3 / \ / 4 5 6 / \ / \ 7 8 9 10 Ouput: [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 leaves are node 4,7,8,9,10. The right boundary are node 1,3,6,10. (10 is the right-most node). So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
 
// get all leaf nodes (left to right)
var preOrder = function(root, level, leafs) {
    if (!root) return;
    if (!root.left && !root.right && level !== 0) leafs.push(root.val);    
    preOrder(root.left, level+1, leafs);
    preOrder(root.right, level+1, leafs);
}
 
var boundaryOfBinaryTree = function(root) {
 
    if (!root) return [];
 
    // get all left boundary nodes
    let leftList = [];
    let curr = root.left;
    while (curr) {
        leftList.push(curr.val);
        if (curr.left) curr = curr.left;
        else curr = curr.right;
    }
    // without the leftmost leaf (because that will already be part of the leaf's list)
    leftList.pop();
 
    // get all right boundary nodes
    let rightList = [];
    curr = root.right;
    while (curr) {
        rightList.push(curr.val);
        if (curr.right) curr = curr.right;
        else curr = curr.left;
    }
    // without the rightmost leaf (because that will already be part of the leaf's list)
    rightList.pop();
 
    // get all leaf nodes
    let leafList = [];
    preOrder(root, 0, leafList);
 
    // Solution is:
    // Root All_Left_Nodes All_Leaf_Nodes Reverse(All_Right_Nodes)
    // Remember to remove last leaf node from All_Left_Nodes and All_Right_Nodes otherwise you will double count!
 
    return ([root.val]).
            concat(leftList).
            concat(leafList).
            concat(rightList.reverse());
};

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ // get all leaf nodes (left to right) var preOrder = function(root, level, leafs) { if (!root) return; if (!root.left && !root.right && level !== 0) leafs.push(root.val); preOrder(root.left, level+1, leafs); preOrder(root.right, level+1, leafs); } var boundaryOfBinaryTree = function(root) { if (!root) return []; // get all left boundary nodes let leftList = []; let curr = root.left; while (curr) { leftList.push(curr.val); if (curr.left) curr = curr.left; else curr = curr.right; } // without the leftmost leaf (because that will already be part of the leaf's list) leftList.pop(); // get all right boundary nodes let rightList = []; curr = root.right; while (curr) { rightList.push(curr.val); if (curr.right) curr = curr.right; else curr = curr.left; } // without the rightmost leaf (because that will already be part of the leaf's list) rightList.pop(); // get all leaf nodes let leafList = []; preOrder(root, 0, leafList); // Solution is: // Root All_Left_Nodes All_Leaf_Nodes Reverse(All_Right_Nodes) // Remember to remove last leaf node from All_Left_Nodes and All_Right_Nodes otherwise you will double count! return ([root.val]). concat(leftList). concat(leafList). concat(rightList.reverse()); };