Introduction To
Binary Search Trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store "items" (such as numbers, names etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by name).
A BST is considered a data structure made up of nodes, like Linked Lists. These nodes are either null or have references (links) to other nodes. These ‘other’ nodes are child nodes, called a left node and right node. Nodes have values. These values determine where they are placed within the BST.
For a binary tree to be a binary search tree, the data of all the nodes in the left sub-tree of the root node should be ≤ the data of the root. The data of all the nodes in the right subtree of the root node should be > the data of the root.
Course Structure
Construction and Conversion
- Construct BST from given preorder traversal | Set 1
- Construct BST from given preorder traversal | Set 2
- Binary Tree to Binary Search Tree Conversion
- Sorted Linked List to Balanced BST
- Sorted Array to Balanced BST
- Transform a BST to greater sum tree
- Construct all possible BSTs for keys 1 to N
- Convert a BST to a Binary Tree such that sum of all greater keys is added to every key
- BST to a Tree with sum of all smaller keys
- In-place Convert BST into a Min-Heap
- Construct BST from its given level order traversal
- Binary Tree to Binary Search Tree Conversion using STL set
- Check given array of size n can represent BST of n levels or not
- Convert a normal BST to Balanced BST
- Merge two BSTs with limited extra space
Self-Balancing BSTs
Checking and Searching
- Find the node with minimum value in a Binary Search Tree
- Check if the given array can represent Level Order Traversal of Binary Search Tree
- Lowest Common Ancestor in a Binary Search Tree.
- A program to check if a binary tree is BST or not
- Find k-th smallest element in BST (Order Statistics in BST)
- Check if each internal node of a BST has exactly one child
- Check for Identical BSTs without building the trees
- K’th Largest Element in BST when modification to BST is not allowed
- K’th Largest element in BST using constant extra space
- Second largest element in BST
- K’th smallest element in BST using O(1) Extra Space
- Check if given sorted sub-sequence exists in binary search tree
- Simple Recursive solution to check whether BST contains dead end
- Check if an array represents Inorder of Binary Search tree or not
- Check if two BSTs contain same set of elements
- Largest number in BST which is less than or equal to N
- Maximum Unique Element in every subarray of size K
- Iterative searching in Binary Search Tree
- Shortest distance between two nodes in BST
- Count pairs from two BSTs whose sum is equal to a given value x
- Find median of BST in O(n) time and O(1) space
- Largest BST in a Binary Tree | Set 2
- Remove BST keys outside the given range
- Print BST keys in the given range
- Print BST keys in given Range | O(1) Space
- Count BST nodes that lie in a given range
- Count BST subtrees that lie in given range
- Remove all leaf nodes from the binary search tree
- Sum of k smallest elements in BST
- Inorder Successor in Binary Search Tree
- Inorder predecessor and successor for a given key in BST
- Inorder predecessor and successor for a given key in BST | Iterative Approach
- Find if there is a triplet in a Balanced BST that adds to zero
- Find a pair with given sum in a Balanced BST
- Find a pair with given sum in BST
- Maximum element between two nodes of BST
- Find pairs with given sum such that pair elements lie in different BSTs
- Find the closest element in Binary Search Tree
- Find the largest BST subtree in a given Binary Tree | Set 1
- Replace every element with the least greater element on its right
- Add all greater values to every node in a given BST
Red Black Tree and Threaded Binary Tree
- Left Leaning Red Black Tree (Insertion)
- Threaded Binary Tree | Insertion
- Threaded Binary Search Tree | Deletion
- Convert a Binary Tree to Threaded binary tree | Set 1 (Using Queue)
- Convert a Binary Tree to Threaded binary tree | Set 2 (Efficient)
- Threaded Binary Tree
- Inorder Non-threaded Binary Tree Traversal without Recursion or Stack
Misc
- Sorted order printing of a given array that represents a BST
- Two nodes of a BST are swapped, correct the BST
- Floor and Ceil from a BST
- Given n appointments, find all conflicting appointments
- Data Structure for a single resource reservations
- How to implement decrease key or change key in Binary Search Tree?
- Print Common Nodes in Two Binary Search Trees
- Count inversions in an array | Set 2 (Using Self-Balancing BST)
- Leaf nodes from Preorder of a Binary Search Tree
- Leaf nodes from Preorder of a Binary Search Tree (Using Recursion)
- Binary Search Tree insert with Parent Pointer
- Minimum Possible value of |ai + aj – k| for given array and k.
- Rank of an element in a stream
- Special two digit numbers in a Binary Search Tree