dailycodingproblem
December 18, 2019

# 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 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 output = [`\${this.value}`]

if (this.left != null) {
}

if (this.right != null) {
}

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 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 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 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:

1. 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.