Published Nov 24, 2021
[
Write a function, depthFirstValues, that takes in the root of a binary tree. The function should return an array containing all values of the tree in depth-first order.
class Node {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
const depthFirstValues = (root) => {
// think of base case & return type
if(root === null) return []
return [root.val, ...depthFirstValues(root.left), ...depthFirstValues(root.right)]
};
const depthFirstValuesStack = (root) => {
// special case handling
if(root === null) return []
const stack = [root]
const res = []
while(stack.length > 0) {
const current = stack.pop()
res.push(current.val)
if(current.right) stack.push(current.right)
if(current.left) stack.push(current.left)
}
return res
}
{
const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
const f = new Node('f');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
// a
// / \
// b c
// / \ \
// d e f
console.log(
depthFirstValues(a));
console.log(
depthFirstValuesStack(a));
// -> ['a', 'b', 'd', 'e', 'c', 'f']
}
{
const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
const f = new Node('f');
const g = new Node('g');
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
e.left = g;
// a
// / \
// b c
// / \ \
// d e f
// /
// g
console.log(
depthFirstValues(a));
console.log(
depthFirstValuesStack(a));
// -> ['a', 'b', 'd', 'e', 'g', 'c', 'f']
}
{
const a = new Node('a');
// a
console.log(
depthFirstValues(a));
console.log(
depthFirstValuesStack(a));
// -> ['a']
}
{
const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
a.right = b;
b.left = c;
c.right = d;
d.right = e;
// a
// \
// b
// /
// c
// \
// d
// \
// e
console.log(
depthFirstValues(a));
console.log(
depthFirstValuesStack(a));
// -> ['a', 'b', 'c', 'd', 'e']
}
{
console.log(
depthFirstValues(null));
console.log(
depthFirstValuesStack(null));
// -> []
}