Binary Trees
I recently subscribed to the dailycodingproblem.com. Every morning they send out a coding challenge based on an interview question. The challenges don’t take that long to solve - but I find I often learn something along the way.
Here is my take on solving todays challenge.
The Challenge
Implement locking in a binary tree. A binary tree node can be locked or unlocked only if all of its descendants or ancestors are not locked.
Design a binary tree node class with the following methods:
is_locked
, which returns whether the node is locked
lock
, which attempts to lock the node. If it cannot be locked, then it should return false. Otherwise, it should lock it and return true.
unlock
, which unlocks the node. If it cannot be unlocked, then it should return false. Otherwise, it should unlock it and return true.You may augment the node to add parent pointers or any other property you would like. You may assume the class is used in a single-threaded program, so there is no need for actual locks or mutexes. Each method should run in O(h), where h is the height of the tree.
What is a Binary Tree?
I don’t come across Binary Tree’s that often in web development, so I had to look up the definition on Wikipedia…
In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
So, it’s like an upside down ancestry chart.
Initial class
Let’s start building out our Binary Tree class. This isn’t going to support locking yet, but it will have the required methods.
class BinaryTreeNode<Value> {
public readonly value: Value
public readonly left?: BinaryTreeNode<Value>
public readonly right?: BinaryTreeNode<Value>
public constructor (
value: Value,
left?: BinaryTreeNode<Value>,
right?: BinaryTreeNode<Value>,
) {
this.value = value
this.left = left
this.right = right
}
public isLocked () {
// renamed from is_locked because we are using camelCase for consistency.
// todo
return false
}
public lock () {
// todo
return false
}
public unlock () {
// todo
return false
}
}
We can use it like this:
const Hannah = new BinaryTreeNode<string>('Hannah')
const Thomas = new BinaryTreeNode<string>('Thomas')
const Emily = new BinaryTreeNode<string>('Emily', Hannah, Thomas)
If we console.log
out the Emily
node - we can see what our tree looks like.
console.log(JSON.stringify(Emily, null, 2))
{
"value": "Emily",
"left": {
"value": "Hannah"
},
"right": {
"value": "Thomas"
}
}
Creating a larger tree
Let’s add a static method that takes this JSON object and creates a tree from it.
For example, we should be able to use it like so:
BinaryTreeNode.from({
value: 'Emily',
left: {
value: 'Hannah'
},
right: {
value: 'Thomas'
}
})
A recursive implementation could look like this:
interface BinaryTreeNodeJSON<Value> {
value: Value,
left?: BinaryTreeNodeJSON<Value>,
right?: BinaryTreeNodeJSON<Value>,
}
class BinaryTreeNode<Value> {
static from<Value> (json: BinaryTreeNodeJSON<Value>): BinaryTreeNode<Value> {
const { value, left, right } = json
const leftNode = left != null ? BinaryTreeNode.from(left) : undefined
const rightNode = right != null ? BinaryTreeNode.from(right) : undefined
return new BinaryTreeNode(value, leftNode, rightNode)
}
// ...
}
Now we can construct a larger Binary Tree quite easily:
const familyTree = BinaryTreeNode.from({
value: 'Emily',
left: {
value: 'Thomas',
left: {
value: 'Daniel',
left: { value: 'Grace' },
right: { value: 'Matthew' },
},
right: {
value: 'Olivia',
left: { value: 'Georgia' },
right: { value: 'Liam' },
}
},
right: {
value: 'Hannah',
left: {
value: 'Emma',
left: { value: 'Jessica' },
right: { value: 'Joshua' },
},
right: {
value: 'Jack',
left: { value: 'Sophie' },
right: { value: 'James' },
}
},
})
Pretty Print
We can add a recursive toString
method to format our tree in a pretty way.
This will make it easy to debug the state of the tree later.
public toString (leftpad = 0): string {
const padding = new Array(leftpad).fill(' ').join('')
const output = [`${this.value}`]
if (this.left != null) {
output.push(`${padding} ⤷ ${this.left.toString(leftpad + 3)}`)
}
if (this.right != null) {
output.push(`${padding} ⤷ ${this.right.toString(leftpad + 3)}`)
}
return output.join('\n')
}
console.log(familyTree.toString())
Emily
⤷ Thomas
⤷ Daniel
⤷ Grace
⤷ Matthew
⤷ Olivia
⤷ Georgia
⤷ Liam
⤷ Hannah
⤷ Emma
⤷ Jessica
⤷ Joshua
⤷ Jack
⤷ Sophie
⤷ James
Locked Out
Okay, now we have a Binary Tree implementation, we can think about locking.
Let’s add a locked
property to our class. This will track if a particular
node is locked or not.
class BinaryTreeNode<Value> {
private locked: boolean
public readonly value: Value
public readonly left?: BinaryTreeNode<Value>
public readonly right?: BinaryTreeNode<Value>
public constructor (
value: Value,
left?: BinaryTreeNode<Value>,
right?: BinaryTreeNode<Value>,
) {
this.value = value
this.left = left
this.right = right
this.locked = false }
public isLocked () {
return this.locked }
public lock () {
this.locked = true return true }
public unlock () {
this.locked = false return true }
// ...
}
Let’s add a little lock icon to our toString
method, so we can see which
nodes are locked.
public toString(leftpad = 0): string {
const padding = new Array(leftpad).fill(' ').join('')
const output = [`${this.value}${this.isLocked() ? '🔒' : ''}`] // ...
}
Now, we can lock the root of the tree:
familyTree.lock()
console.log(familyTree.toString())
Emily🔒
⤷ Thomas
⤷ Daniel
⤷ Grace
⤷ Matthew
⤷ Olivia
⤷ Georgia
⤷ Liam
⤷ Hannah
⤷ Emma
⤷ Jessica
⤷ Joshua
⤷ Jack
⤷ Sophie
⤷ James
However, this doesn’t stop us from locking any other node in the tree.
familyTree.left.lock()
familyTree.right.lock()
console.log(familyTree.toString())
Emily🔒
⤷ Thomas🔒
⤷ Daniel
⤷ Grace
⤷ Matthew
⤷ Olivia
⤷ Georgia
⤷ Liam
⤷ Hannah🔒
⤷ Emma
⤷ Jessica
⤷ Joshua
⤷ Jack
⤷ Sophie
⤷ James
Looking back at the original problem:
A binary tree node can be locked or unlocked only if all of its descendants or ancestors are not locked.
So we need to make sure that none of the descendants or ancestors are locked, before we lock a particular node.
Every Child
We are going to need a way to loop through every child of a node, and test if they every single one of them is unlocked.
JavaScript arrays have this neat method called every
. You can read more about
it on MDN: Array.prototype.every
.
The
every()
method tests whether all elements in the array pass the test implemented by the provided function. It returns a Boolean value.
We can build a similar method for our Binary Tree class. Let’s call it
everyChild
- this will hint to anyone using our class how to use it.
public everyChild (fn: (node: BinaryTreeNode<Value>) => boolean): boolean {
if (this.left != null && (!fn(this.left) || !this.left.everyChild(fn))) {
return false
}
if (this.right != null && (!fn(this.right) || !this.right.everyChild(fn))) {
return false
}
return true
}
Every Parent
We will also need something similar for every parent.
However, we currently don’t have a way of accessing the parent of a node. We will need to add another property to our class!
class BinaryTreeNode<Value> {
// ...
public readonly left?: BinaryTreeNode<Value>
public readonly right?: BinaryTreeNode<Value>
public parent?: BinaryTreeNode<Value>
public constructor (
value: Value,
left?: BinaryTreeNode<Value>,
right?: BinaryTreeNode<Value>,
) {
this.value = value
this.left = left
if (this.left != null) { this.left.setParent(this) } this.right = right
if (this.right != null) { this.right.setParent(this) } this.locked = false
}
public setParent (parent: BinaryTreeNode<Value>) { this.parent = parent }
Now we can add an everyParent
method.
public everyParent (fn: (node: BinaryTreeNode<Value>) => boolean): boolean {
if (this.parent != null && (!fn(this.parent) || !this.parent.everyParent(fn))) {
return false
}
return true
}
Bringing it all together
We are ready to implement our lock
and unlock
functions now.
private everyParentUnlocked () {
return this.everyParent((node) => !node.isLocked())
}
private everyChildUnlocked () {
return this.everyChild((node) => !node.isLocked())
}
public lock () {
if (!this.everyParentUnlocked() || !this.everyChildUnlocked()) {
return false
}
this.locked = true
return true
}
public unlock () {
if (!this.everyParentUnlocked() || !this.everyChildUnlocked()) {
return false
}
this.locked = false
return true
}
Cool! Now let’s test it out:
familyTree.lock() // true
familyTree.left.lock() // false
familyTree.right.lock() // false
console.log(familyTree.toString())
Emily🔒
⤷ Thomas
⤷ Daniel
⤷ Grace
⤷ Matthew
⤷ Olivia
⤷ Georgia
⤷ Liam
⤷ Hannah
⤷ Emma
⤷ Jessica
⤷ Joshua
⤷ Jack
⤷ Sophie
⤷ James
We can even unlock the root and lock a child. This prevents the parent from being relocked.
familyTree.unlock() // truefamilyTree.left.lock() // true
familyTree.right.lock() // true
familyTree.lock() // false
console.log(familyTree.toString())
Emily
⤷ Thomas🔒
⤷ Daniel
⤷ Grace
⤷ Matthew
⤷ Olivia
⤷ Georgia
⤷ Liam
⤷ Hannah🔒
⤷ Emma
⤷ Jessica
⤷ Joshua
⤷ Jack
⤷ Sophie
⤷ James
I’m going to stop here. You can read the entire source code file on Github.
Future ideas:
- The challenge mentions that each method should run in O(h). I’m not quite sure if my implementation meets this requirement. Recursively iterating over all children of a node would be O(2^h - 1). I don’t know how you would improve on this.