Categories
interview

Binary Tree Right Side View

var root = {
   val: 1,
   left: {
           val: 2,
           left: null,
           right: {
                   val: 5,
                   left: null,
                   right: null
                  }
          },
  right: {
           val: 3,
           left: null,
           right: {
                   val: 4,
                   left: null,
                   right: null
                  }
          }
};
/*
  1
 /  \
2    3
 \    \
  5    4
*/

var node = function(node, depth) {
  this.node = node;
  this.depth = depth;
};

var rightSideView = function(root) {
  if (root === null)
    return [];
  var q = [];
  var ret = [];
  var level = 0;
  var prev;
  q.push(new node(root, 0));
  while (q.length > 0) {
    var curr = q.shift();
    if (curr.depth > level) {
      ret.push(prev.node.val);
      level = curr.depth;
    }
    prev = curr;
    if (curr.node.left) {
      q.push(new node(curr.node.left, curr.depth + 1));
    }
    if (curr.node.right) {
      q.push(new node(curr.node.right, curr.depth + 1));
    }
  }
  ret.push(prev.node.val);
  return ret;
};

console.log(rightSideView(root));
// Output: [1, 3, 4]

Demo