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
- Is This a Binary Search Tree? | HackerRank
- Binary Search Tree : Lowest Common Ancestor | HackerRank
- Binary Search Tree : Insertion | HackerRank
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 = []
// 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
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!
Top comments (2)
Good article!!!