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