Binary Search Tree (My Personal Google Interview Study Notes)
Tags: datastructure, binarytree, binarysearchtree, faang
Published: 2021-07-10 05:04:51

[![Twitter Follow](https://img.shields.io/twitter/follow/cleancodestudio.svg?style=social)](https://twitter.com/cleancodestudio) 


> _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](https://www.cleancode.studio/notes/faang-interview-notes)

---

## Binary Tree Practice

---

* [Is This a Binary Search Tree? | HackerRank](https://www.hackerrank.com/challenges/is-binary-search-tree/problem)
* [Binary Search Tree : Lowest Common Ancestor | HackerRank](https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem)
* [Binary Search Tree : Insertion | HackerRank](https://www.hackerrank.com/challenges/binary-search-tree-insertion/problem)

## 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)](https://www.cleancode.studio/notes/faang-interview-notes)

[Clean Code](https://cleancode.studio/clean-code)
[Clean Code Studio](https://cleancode.studio)
 
[Github Data Structures & Algorithms 101 (Using JS)](https://github.com/zhorton34/data-structures-algorithms-101)

[Binary Tree Node](https://github.com/zhorton34/data-structures-algorithms-101/blob/master/src/structures/BinaryTreeNode.js)
```js
/*------------------------------------------------------------------------------------
 |   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
```

[Binary Search Tree](https://github.com/zhorton34/data-structures-algorithms-101/blob/master/src/structures/BinarySearchTree.js)
```js
// 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
```
--- 
> **FAANG Study Resource: Cracking the Coding Interview**
> (Google Recommended)

<a target="_blank"  href="https://www.amazon.com/gp/product/0984782850/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=0984782850&linkCode=as2&tag=ccs0cc-20&linkId=4e21ded6a61b9a202cdc2b9c0bd14025"><img border="0" src="//ws-na.amazon-adsystem.com/widgets/q?_encoding=UTF8&MarketPlace=US&ASIN=0984782850&ServiceVersion=20070822&ID=AsinImage&WS=1&Format=_SL250_&tag=ccs0cc-20" ></a>


---


[My FAANG interview study notes](https://www.cleancode.studio/notes/faang-interview-notes)


[Clean Code](https://cleancode.studio/clean-code)
[Clean Code Studio](https://cleancode.studio)
[Clean Code Clean Life ~ Simplify](https://cleancode.studio)


**Subscribe to the Clean Code Studio Newsletter!**

{% codepen https://codepen.io/zhorton34/pen/BaRPYdB %}