DEV Community

loading...
Cover image for Binary Search Tree (My Personal Google Interview Study Notes)

Binary Search Tree (My Personal Google Interview Study Notes)

Clean Code Studio
Clean Code Clean Life ~ Simplify
Updated on ・5 min read

Twitter Follow

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

See all of my Google, Amazon, & Facebook interview study notes


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

Check out my FAANG interview study notes (70+ documents worth of resources)

Clean Code
Clean Code Studio

Github Data Structures & Algorithms 101 (Using JS)

Binary Tree Node

/*------------------------------------------------------------------------------------
 |   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
Enter fullscreen mode Exit fullscreen mode

Binary Search Tree

// 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
Enter fullscreen mode Exit fullscreen mode

FAANG Study Resource: Cracking the Coding Interview
(Google Recommended)


My FAANG interview study notes

Clean Code
Clean Code Studio
Clean Code Clean Life ~ Simplify

Subscribe to the Clean Code Studio Newsletter!

Discussion (1)

Collapse
cleancodestudio profile image
Clean Code Studio Author