Skip to content

Instantly share code, notes, and snippets.

@jasonsperske
Last active July 12, 2017 20:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jasonsperske/8339280 to your computer and use it in GitHub Desktop.
Save jasonsperske/8339280 to your computer and use it in GitHub Desktop.
Find the deepest left most node in a binary tree (and it's depth). A working demo can be found at: http://jsfiddle.net/YfLx6/5/
var Node = function(name, left, right) {
this.name = name;
this.left = left;
this.right = right;
},
findDeepest = function(node, depth) {
var left, right, depth = depth || 0;
if(typeof node !== 'undefined') {
left = findDeepest(node.left, depth+1);
right = findDeepest(node.right, depth+1);
if(typeof left !== 'undefined' && typeof right !== 'undefined') {
if(left.depth >= right.depth) {
return left;
} else {
return right;
}
} else if(typeof left !== 'undefined') {
return left;
} else if(typeof right !== 'undefined') {
return right;
} else {
return {node: node, depth: depth};
}
}
};
//Now to test it
var deepest = findDeepest(
new Node('A',
/* \
/ \
/ \
/ */
new Node('B'), new Node('C',
/* \
/ \
/ \
/ */
new Node('D'), new Node('E'))));
alert("Found '" + deepest.node.name + "' at depth of "+deepest.depth);
//returns "Found 'D' at depth of 2"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment