Binary Search Trees — Simple English

77 lessons · Data Structures & Algorithms · Simple English · Beginner Friendly

01 Understanding a Binary Search TreeFree Understanding a Binary Search Tree A binary search tree (often shortened to BST) is a special way of storing data. Befor… 02 The Structure of a Binary Search TreeFree What Is a Binary Search Tree? A binary tree is a tree where every node can have at most two children — a left child and … 03 Special Properties of a Binary Search TreeFree Special Properties of a Binary Search Tree A binary search tree is just a binary tree that follows one simple rule. We c… 04 How Binary Search Trees Are Stored in Memory🔒 How Binary Search Trees Are Stored in Memory A binary search tree (BST) is just a binary tree that follows some extra ru… 05 How a Tree's Height Affects Its Speed🔒 How a Tree's Height Affects Its Speed In a binary search tree, every operation you do — searching for a value, inserting… 06 Balance Factor: Measuring How Good a Binary Search Tree Is🔒 Balance Factor: Measuring How Good a Binary Search Tree Is We already know that not all binary search trees are equally … 07 Balance Factor of a Binary Search Tree🔒 Balance Factor of a Binary Search Tree When we work with trees, we often want to know if a tree is "even" or "lopsided."… 08 Balance Factor of a Subtree in a Binary Search Tree🔒 Balance Factor of a Subtree Imagine a tree made of nodes. Each node can have a node hanging on its left and a node hangi… 09 Why We Cannot Use Complete Binary Search Trees in Practice🔒 Why We Cannot Use Complete Binary Search Trees in Practice A binary search tree (BST) is a tree where every node has at … 10 Height-Balanced Binary Trees🔒 Height-Balanced Binary Trees Earlier we saw a problem. A complete binary tree is the most perfect shape a binary search … 11 Checking if a Binary Tree is Height-Balanced🔒 Checking if a Binary Tree is Height-Balanced When we build a tree, we often care about its shape, not just the values in… 12 Searching a Binary Search Tree with Recursion🔒 Searching a Binary Search Tree with Recursion A binary search tree (BST) is a special kind of tree where the values are … 13 Searching for a Value in a Binary Search Tree (Recursively)🔒 Searching a Binary Search Tree A binary search tree (BST for short) is a special way of organizing data. It is a tree ma… 14 Finding the Minimum Value in a Binary Search Tree (Recursively)🔒 Finding the Minimum Value in a Binary Search Tree A binary search tree (BST) is a tree where every node follows one simp… 15 Finding the Smallest Value in a Binary Search Tree (Recursively)🔒 Finding the Smallest Value in a Binary Search Tree A binary search tree (often called a BST) is a special way of storing… 16 Finding the Maximum Value in a Binary Search Tree (Recursively)🔒 Finding the Maximum Value in a Binary Search Tree A binary search tree (BST) is a tree where every node follows one simp… 17 Finding the Maximum Value in a Binary Search Tree (Using Recursion)🔒 Finding the Largest Value in a Binary Search Tree Imagine a special kind of tree where every piece of data is arranged n… 18 Finding the Lower Bound in a Binary Search Tree (Recursively)🔒 Finding the Lower Bound in a Binary Search Tree What "lower bound" means The lower bound of a value is the smallest numb… 19 Finding the Lower Bound in a Binary Search Tree (Recursively)🔒 Finding the Lower Bound in a Binary Search Tree What is a lower bound? Imagine you have a sorted list of numbers and you… 20 Finding the Upper Bound of a Value in a Binary Search Tree (Recursion)🔒 Finding the Upper Bound in a Binary Search Tree The upper bound of a value means the smallest number in the tree that is… 21 Finding the Upper Bound in a Binary Search Tree (Recursively)🔒 Finding the Upper Bound in a Binary Search Tree What "upper bound" means The upper bound of a target value is the smalle… 22 Searching a Binary Search Tree with a Loop (Iterative Search)🔒 Searching a Binary Search Tree Without Recursion A binary search tree (BST) has one special rule that makes searching fa… 23 Searching a Binary Search Tree Without Recursion🔒 Searching a Binary Search Tree Without Recursion Imagine you have a special kind of tree that stores numbers in a very o… 24 Finding the Smallest Value in a BST Using a Loop🔒 Finding the Smallest Value in a BST Using a Loop A binary search tree (BST) is a tree of nodes where every node follows … 25 Finding the Smallest Value in a Binary Search Tree (Without Recursion)🔒 Finding the Smallest Value in a Binary Search Tree Imagine you have a special kind of tree of numbers called a binary se… 26 Finding the Maximum Value in a Binary Search Tree (Using a Loop)🔒 Finding the Maximum Value in a Binary Search Tree (Using a Loop) A binary search tree (BST) is a special way of storing … 27 Finding the Maximum Value in a Binary Search Tree (Without Recursion)🔒 Finding the Maximum Value in a Binary Search Tree Imagine you have a special kind of tree of numbers, and you want to fi… 28 Finding the Lower Bound in a Binary Search Tree (Iterative Way)🔒 Finding the Lower Bound Without Recursion The lower bound of a value is the smallest number in the tree that is greater … 29 Finding the Lower Bound in a Binary Search Tree (Without Recursion)🔒 Finding the Lower Bound in a Binary Search Tree Imagine you have a sorted list of numbers and someone gives you a target… 30 Finding the Upper Bound in a Binary Search Tree (Iterative Way)🔒 Finding the Upper Bound in a Binary Search Tree (Iterative Way) What is an "upper bound"? The upper bound of a value is … 31 Finding the Upper Bound in a Binary Search Tree (Iteratively)🔒 Finding the Upper Bound in a Binary Search Tree Sometimes you don't just want to know if a value exists in a tree. You w… 32 Finding the Closest Value in a Binary Search Tree🔒 Finding the Closest Value in a Binary Search Tree Imagine you have a collection of numbers organized in a special way, a… 33 Inserting a Node into a Binary Search Tree (Recursion)🔒 Inserting a Value into a Binary Search Tree A binary search tree (BST) is a tree where every node follows one simple rul… 34 Inserting a New Node into a Binary Search Tree (Recursively)🔒 Adding a Value to a Binary Search Tree A binary search tree (BST for short) is a special way of storing numbers so they … 35 Inserting a Value into a Binary Search Tree Using a Loop (Iterative Insertion)🔒 Iterative Insertion in a Binary Search Tree A binary search tree (BST) is a tree where every node has at most two childr… 36 Inserting a New Node into a Binary Search Tree (Without Recursion)🔒 Inserting a New Node into a Binary Search Tree A binary search tree (BST for short) is a special way of arranging number… 37 Deleting a Node from a Binary Search Tree🔒 Deleting a Node from a Binary Search Tree When you remove a value from a binary search tree (BST), you cannot just rip t… 38 Finding the Inorder Successor in a Binary Search Tree🔒 Finding the Inorder Successor in a Binary Search Tree When we walk through a Binary Search Tree (BST) in a special order… 39 Deleting a Node from a Binary Search Tree (Recursively)🔒 Deleting a Node from a Binary Search Tree A binary search tree (BST for short) is a special way of storing numbers in a … 40 Deleting a Value from a Binary Search Tree the Iterative Way🔒 Deleting a Value from a Binary Search Tree the Iterative Way We already know how to add a value to a binary search tree … 41 Deleting a Node from a Binary Search Tree (Without Recursion)🔒 Deleting a Node from a Binary Search Tree (Without Recursion) A binary search tree (BST) is a tree where every node hold… 42 Building a Balanced Binary Search Tree from a Sorted Array🔒 Building a Balanced Binary Search Tree from a Sorted Array When you walk through a binary search tree (BST) "in order" —… 43 Building a Balanced Binary Search Tree from a Sorted Array🔒 Building a Balanced Binary Search Tree from a Sorted Array Imagine you already have a list of numbers neatly arranged fr… 44 Building a Binary Search Tree from an Unsorted Array🔒 Building a Binary Search Tree from an Unsorted Array Suppose you are given a plain list of numbers in no particular orde… 45 Building a Binary Search Tree from an Unsorted Array🔒 Building a Binary Search Tree from an Unsorted Array Imagine you are given a plain list of numbers in no particular orde… 46 Building a Balanced Binary Search Tree from a Sorted Linked List🔒 Building a Balanced Binary Search Tree from a Sorted Linked List Imagine you have a list of numbers that is already sort… 47 Finding the Lowest Common Ancestor in a Binary Search Tree🔒 Finding the Lowest Common Ancestor in a Binary Search Tree Imagine a family tree. Two people might be cousins, and their… 48 Lowest Common Ancestor in a Binary Search Tree🔒 Finding the Lowest Common Ancestor Imagine a family tree. Two people in the family both have parents, grandparents, and … 49 Iterators in Binary Search Trees: Visiting Nodes One at a Time🔒 Iterators in Binary Search Trees The special order hidden inside a binary search tree A binary search tree (BST) is a tr… 50 The Forward BST Iterator: Walking a Binary Search Tree in Sorted Order, One Node at a Time🔒 The Forward BST Iterator: Sorted Order on Demand A binary search tree (BST) is a tree where, for every node, all the sma… 51 Designing a Forward BST Iterator (In-Order Traversal)🔒 Designing a Forward BST Iterator Sometimes you don't want to read a whole tree all at once. You want to walk through its… 52 The Reverse BST Iterator: Walking a Tree from Largest to Smallest🔒 The Reverse BST Iterator: Walking a Tree from Largest to Smallest A binary search tree (BST) keeps its values in a neat … 53 Building a Reverse BST Iterator (Step Through a Tree from Biggest to Smallest)🔒 Building a Reverse BST Iterator A binary search tree (BST) is a tree where every node holds a value, and for each node, … 54 The Sorted Traversal Pattern in a Binary Search Tree🔒 The Sorted Traversal Pattern in a Binary Search Tree Sometimes you have a binary search tree, and you need to walk throu… 55 The Sorted Traversal Pattern in Binary Search Trees🔒 What the sorted traversal pattern is A binary search tree (BST) is a tree where, for every node, all the smaller values … 56 Lowest Absolute Variance in a Binary Search Tree🔒 Lowest Absolute Variance in a Binary Search Tree This is a classic problem that uses a special kind of tree called a Bin… 57 Checking if a Binary Tree Is a Valid Binary Search Tree🔒 Checking if a Binary Tree Is a Valid Binary Search Tree A binary tree is a structure where each box, called a node, hold… 58 Turning a Binary Search Tree Into a Sorted Array🔒 Turning a Binary Search Tree Into a Sorted Array Imagine you have a special kind of tree of numbers, and your goal is to… 59 Converting a Binary Search Tree into a Sorted Doubly Linked List🔒 Turning a BST into a Sorted Doubly Linked List This lesson takes two ideas you already know and connects them. First, a … 60 The Reverse Sorted Traversal Pattern in a Binary Search Tree🔒 Visiting a BST from Largest to Smallest Sometimes a problem asks you to look at the values in a binary search tree start… 61 The Reverse Sorted Traversal Pattern in a Binary Search Tree🔒 The Reverse Sorted Traversal Pattern A binary search tree (BST) is a tree where, for every node, all the smaller values … 62 Ranking BST Nodes in Descending Order🔒 Ranking BST Nodes in Descending Order Imagine a classroom where students are lined up by their marks. The student with t… 63 Finding the Kth Largest Element in a Binary Search Tree🔒 Finding the Kth Largest Element in a BST A binary search tree (BST) is a special kind of tree where every node follows o… 64 Enriched Sum Tree: Add Every Greater Value to Each Node🔒 Enriched Sum Tree What we are trying to do We start with a binary search tree (BST). A BST is a tree where, for every no… 65 Replacing BST Nodes Based on Their Successor🔒 Replacing BST Nodes Based on Their Successor This lesson works through a tree problem. You are given the top node (the r… 66 The Range Postorder Pattern in Binary Search Trees🔒 The Range Postorder Pattern in Binary Search Trees A quick reminder about binary search trees A binary search tree (BST)… 67 The Range Postorder Pattern in Binary Search Trees🔒 The Range Postorder Pattern Some binary search tree problems hand you a range — a low value and a high value — and ask y… 68 Range Summation in a Binary Search Tree🔒 Range Summation in a Binary Search Tree Imagine a family tree where each person has a number. You are given a binary sea… 69 Finding the Diameter of a Subtree Within a Range in a BST🔒 Range Diameter in a Binary Search Tree This lesson brings together two ideas you may have seen before: a binary search t… 70 Counting In-Range Leaves and Storing the Count in Each Parent Node🔒 Counting In-Range Leaves in a Binary Search Tree This lesson works through a tree problem step by step. Don't worry if s… 71 Trimming a Binary Search Tree to a Range🔒 Trimming a Binary Search Tree to a Range Imagine you have a sorted collection of numbers stored in a special shape calle… 72 The Two-Pointer Pattern on a Binary Search Tree🔒 The Two-Pointer Pattern on a Binary Search Tree Why a binary search tree is special A binary search tree (BST) keeps val… 73 The Two-Pointer Pattern in a Binary Search Tree🔒 The Two-Pointer Pattern in a Binary Search Tree Some binary search tree (BST) problems can be solved with a neat trick c… 74 Two Sum on a Binary Search Tree🔒 Two Sum on a Binary Search Tree In this lesson we solve a classic problem. You are given a binary search tree (BST) and … 75 Multiple Tree: Checking Pairs in a BST's In-Order Order🔒 Multiple Tree: Pairing the Smallest with the Largest This lesson works through a coding problem that combines two ideas … 76 Finding the Median Value in a Binary Search Tree🔒 Finding the Median Value in a Binary Search Tree When we talk about the median, we mean the middle value of a group of n… 77 BST Pair Sum: Finding a Pair Across Two Trees That Adds Up to a Target🔒 BST Pair Sum: One Number From Each Tree Imagine you have two separate collections of numbers, and each collection is sto…