Binary Search Tree (My Personal Google Interview Study Notes)

Note: This is not a "professionally written" post. This is a post sharing personal notes I wrote down while preparing for FAANG interviews.

Binary Tree Practice

Binary Search Tree

Binary Tree
Each Node contains a key and an optional associated value
Allows particularly fast lookup, addition, and removal of items

Binary Search Tree ~ Node Arrangement

The left subtree of a particular node
- Contains nodes with keys less than that node’s keys
The right subtree of a particular node
- Contains nodes with keys greater than that node’s keys
The right and left subtree, in turn, will also be binary keys

Binary Search Tree Time Complexity

In average cases, O(log n) where _n _is the number of nodes in the tree
- Insert operation
- Search operation
- Deletion operation
In worst cases, O(n) due to tree becoming unbalanced
- Insert operation
- Search operation
- Deletion operation

Binary Search Tree Space Complexity

The space-complexity of a binary tree is O(n) in average and worst case scenarios

Types of Traversals

Traversals

Pre-order traversal
- Visits nodes in Parent-LeftChild-RightChild order
In-order traversal
- Visits nodes in LeftChild-Parent-RightChild order.
- In this way, the tree is traversed in an ascending order of keys
Post-order traversal
- Visits nodes in LeftChild-RightChild-Parent

/*------------------------------------------------------------------------------------
 |   Binary Tree Node
 *------------------------------------------------------------------------------------
 |
 |   . Api
 |     -> leftHeight
 |        @return {number}
 |     -> rightHeight
 |        @return {number}
 |     -> height
 |        @return {number}
 |     -> balanceFactor
 |        @return {number}
 |     -> uncle
 |        @return {BinaryTreeNode}
 |     -> setValue
 |        @param {*} value
 |        @return {BinaryTreeNode}
 |     -> setLeft
 |        @param {BinaryTreeNode} node
 |        @return {BinaryTreeNode}
 |     -> setRight
 |        @param {BinaryTreeNode} node
 |        @return {BinaryTreeNode}
 |     -> removeChild
 |        @param {BinaryTreeNode} nodeToRemove
 |        @return {boolean}
 |     -> replaceChild
 |        @param {BinaryTreeNode} nodeToReplace
 |        @param {BinaryTreeNode} replacementNode
 |        @return {boolean}
 |     -> copyNode (static)
 |        @param {BinaryTreeNode} sourceNode
 |        @param {BinaryTreeNode} targetNode
 |     -> traverseInOrder
 |        @return {*[]}
 |     -> toString
 |        @return {string}
 |
 */
const HashTable = require('@DataStructure/HashTable.js')
const Comparator = require('@Helper/Comparator')


class BinaryTreeNode 
{
  static make(...parameters)
  {
    return new this(...parameters)
  }

  constructor(data = null) 
  {
    this.data = data
    this.left = null
    this.right = null
    this.parent = null

    // Any node related meta information may be stored here.
    this.meta = HashTable.make()

    // This comparator is used to compare binary tree nodes with each other.
    this.nodeComparator = Comparator.make()
  }


  get leftHeight() 
  {
    if (!this.left) return 0

    return this.left.height + 1
  }

  get rightHeight() 
  {
    if (!this.right) return 0

    return this.right.height + 1
  }

  get height() 
  {
    return Math.max(this.leftHeight, this.rightHeight)
  }

  get balanceFactor() 
  {
    return this.leftHeight - this.rightHeight
  }

  get uncle() 
  {
    if (!this.parent) return undefined

    // Check if current node has grand-parent.
    if (!this.parent.parent) return undefined

    // Check if grand-parent has two children.
    if (!this.parent.parent.left || !this.parent.parent.right) return undefined

    // So for now we know that current node has grand-parent and this
    // grand-parent has two children. Let's find out who is the uncle.
    if (this.nodeComparator.equal(this.parent, this.parent.parent.left)) return this.parent.parent.right

    // Left one is an uncle.
    return this.parent.parent.left
  }

  setValue(value) 
  {
    this.value = value

    return this
  }


  setLeft(node) 
  {
    // Reset parent for left node since it is going to be detached.
    if (this.left) this.left.parent = null

    // Attach new node to the left.
    this.left = node

    // Make current node to be a parent for new left one.
    if (this.left) this.left.parent = this

    return this
  }

  setRight(node) 
  {
    // Reset parent for right node since it is going to be detached.
    if (this.right) this.right.parent = null

    // Attach new node to the right.
    this.right = node

    // Make current node to be a parent for new right one.
    if (node) this.right.parent = this

    return this
  }

  removeChild(nodeToRemove) 
  {
    if (this.left && this.nodeComparator.equal(this.left, nodeToRemove)) {
      this.left = null
      return true
    }

    if (this.right && this.nodeComparator.equal(this.right, nodeToRemove)) {
      this.right = null
      return true
    }

    return false
  }

  replaceChild(nodeToReplace, replacementNode) 
  {
    if (!nodeToReplace || !replacementNode) return false

    if (this.left && this.nodeComparator.equal(this.left, nodeToReplace)) {
      this.left = replacementNode
      return true
    }

    if (this.right && this.nodeComparator.equal(this.right, nodeToReplace)) {
      this.right = replacementNode
      return true
    }

    return false
  }

  static copyNode(sourceNode, targetNode) 
  {
    targetNode.setValue(sourceNode.value)
    targetNode.setLeft(sourceNode.left)
    targetNode.setRight(sourceNode.right)
  }

  traverseInOrder() 
  {
    let traverse = []

    // Add left node.
    if (this.left) {
      traverse = traverse.concat(this.left.traverseInOrder())
    }

    // Add root.
    traverse.push(this.value)

    // Add right node.
    if (this.right) {
      traverse = traverse.concat(this.right.traverseInOrder())
    }

    return traverse
  }

  toString() 
  {
    return this.traverseInOrder().toString()
  }
}

module.exports = BinaryTreeNode

// https://opendatastructures.org/versions/edition-0.1c/ods-java/node36.html


// lookup
// insert
// delete
// access 

// depth
// count
// isEmpty
// isNotEmpty


/** 
 | has(value)
   insert(value)
   lookup(value)
 | delete(value) // TODO: fix this function
 | depthFirstLog (cllback)
*/

class BinarySearchTree 
{
    constructor (value)
    {
      this.value = value 
      this.left = undefined
      this.right = undefined

      return this
    }

    insert (value)
    {
      let node = new BinarySearchTree(value)

      let recurse = bst => {
        if (bst.value > value && bst.left === undefined) {
          bst.left = node
        } else if (bst.value > value) {
          recurse(bst.left)
        } else if (bst.value < value && bst.right === undefined) {
          bst.right = node
        } else if (bst.value < value) {
          recurse(bst.right)
        }
      }

      recurse(this)

    }

    lookup (value)
    {
      let resolved = -1
      let recurse = bst => {
        if (bst.value === value) {
          resolved = bst
        } else if (bst.left !== undefined && value < bst.value) {
          recurse(bst.left)
        } else if (bst.right !== undefined && value > bst.value) {
          recurse(bst.right)
        }
      }

      recurse(this)

      return resolved
    }

    has (value)
    {
      let hasValue = false;
      //accepts a value and returns a boolean reflecting whether or not the value is contained in the tree.
      let recurse = bst => {
        if (bst.value === value) {
          hasValue = true
        } else if (bst.left !== undefined && value < bst.value) {
          recurse(bst.left)
        } else if (bst.right !== undefined && value > bst.value) {
          recurse(bst.right)
        }
      }

      recurse(this)

      return hasValue
    }

    delete (start) 
    {
      let data = []
      let queue = []

      let node = start ? this.lookup(start) : this.root

      queue.push(node)
      while (queue.length) {
        node = queue.shift()
        data.push(node.value)

        if (node.left) queue.push(node.left)
        if (node.right) queue.push(node.right)
      }
    }

    depthFirstLog (callback = console.log)
    {
      let recurse = bst => {
        callback.call(bst, bst.value)

        if (bst.left !== undefined) recurse(bst.left)
        if (bst.right !== undefined) recurse(bst.right)
      }

      recurse(this)
    }
}



module.exports = BinarySearchTree