## DEV Community

Clean Code Studio

Posted on • Updated on

# 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 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)

Github Data Structures & Algorithms 101 (Using 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 = []

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

traverse.push(this.value)

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

FAANG Study Resource: Cracking the Coding Interview

My FAANG interview study notes

Subscribe to the Clean Code Studio Newsletter!