Hide Index

Binary Search Tree

0% completed

Introduction to binary search trees

Understanding a binary search tree

Structure of a binary search tree

Characteristics of a binary search tree

Implementation of binary search trees

Height & balance in binary search trees

Understanding the impact of height on performance

Understanding the balance of a tree

Balance of subtree

Challenges in implementing complete binary search trees

Understanding height balanced binary trees

Height balanced tree

Recursive searching in binary search trees

Understanding recursive search

Implement recursive search

Understanding recursive minimum search

Recursively find minimum

Understanding recursive maximum search

Recursively find maximum

Understanding recursive lower bound search

Recursively find lower bound

Understanding recursive upper bound search

Recursively find upper bound

Iterative searching in binary search trees

Understanding iterative search

Implement iterative search

Understanding iterative minimum search

Iteratively find minimum

Understanding iterative maximum search

Iteratively find maximum

Understanding iterative lower bound search

Iteratively find lower bound

Understanding iterative upper bound search

Iteratively find upper bound

Insertion in binary search trees

Understanding recursive insertion

Recursively insert a node

Understanding iterative insertion

Iteratively insert a node

Deletion in binary search trees

Understanding recursive deletion

Inorder successor

Recursively delete a node

Understanding iterative deletion

Iteratively delete a node

Constructing a binary search tree

Understanding construction from a sorted array

Construct BST from a sorted array

Understanding construction from an unsorted array

Construct BST from an unsorted array

Sorted linked list to BST

Lowest common ansestor in binary search trees

Understanding the lowest common ancestor

Lowest common ancestor

Iterators in a binary search trees

Understanding iterators in binary search trees

Understanding the forward BST iterator

Design a forward BST iterator

Understanding the reverse BST iterator

Design a reverse BST iterator

Pattern: Sorted traversal

Understanding the sorted traversal pattern

Identifying the sorted traversal pattern

Lowest absolute variance

BST to sorted array

Pattern: Reversed sorted traversal

Understanding the reversed sorted traversal pattern

Identifying the reverse sorted traversal pattern

Kth Largest element

Enriched sum tree

newMultiple replacement

Pattern: Range postorder

Understanding the range postorder pattern

Identifying the range postorder pattern

Range summation

newRange diameter

newRange leaves

Range exclusive trim

Pattern: Two pointer

Understanding the two pointer pattern

Identifying the two pointer pattern

newMultiple tree

newMedian in BST

Assessments

Certificate

Understanding recursive search

Searching for a value in a binary search tree can be implemented by piggybacking on any of the binary tree traversal algorithms. However, if we observe the special property of a binary search tree (given below), we can quickly develop an exponentially faster algorithm.

All nodes in a node's `left` subtree are `less in value` than the node's value.

All nodes in a node's `right` subtree are `greater in value` than the node's value.

Algorithm

Liking the course? Check our discounted plans to continue learning.