Skip to content
dsa450for five year olds

Topic 09 of 15

Binary Search Trees

A guessing game tree.

A binary search tree keeps a promise at every node: everything on the left is smaller, everything on the right is bigger. That promise turns searching into a guessing game, "is it smaller or bigger?", and reading it in order gives a sorted list.

What you will be able to do

Search, insert, deleteInorder gives sorted orderValidating with rangesKth smallestLCA by comparing values
0/22
22 problems

Meet the binary search tree

01 / 04

tree
8310161447

Left side smaller, right side bigger, at every node.

  • looking now
  • seen
  • answer
  • path
  • ignored

The problems

In order from easier to harder ideas. The ones marked must do come up in interviews again and again.

  1. 01Find a value in a BSTFind a number in a sorted tree by asking smaller or bigger at every fork, so you only walk one road from the top to the bottom.BST search
  2. 02Deletion of a node in a BSTTake one number out of a sorted tree and patch the hole so every spot still has smaller numbers on the left and bigger ones on the right.BST search and splice
  3. 03Find min and max value in a BSTThe smallest number in a sorted tree lives at the end of the always-go-left road, and the biggest at the end of the always-go-right road.BST search
  4. 04Find inorder successor and inorder predecessor in a BSTFind the number that comes right before and right after a key in sorted order, by walking one road down a sorted tree.BST search
  5. 05Check if a tree is a BST or notCheck that every number in a tree sits inside the window its ancestors allow, so smaller ones are always on the left and bigger ones always on the right.Depth first search with bounds
  6. 06Populate Inorder successor of all nodesGive every spot in a tree an extra arrow that points to the next bigger number, by visiting the numbers from biggest to smallest.Reverse inorder traversal
  7. 07Find LCA of 2 nodes in a BSTFind the lowest spot in a sorted tree that is an ancestor of two given numbers, by walking down until the two numbers want to go different ways.BST search
  8. 08Construct BST from preorder traversalRebuild a sorted tree from the order its numbers were visited top first, by letting each spot accept the next number only if it fits under a ceiling.Depth first search with bounds
  9. 09Convert Binary tree into BSTKeep the exact shape of a tree but move the numbers around so it becomes a sorted tree, by pouring the sorted numbers back in left-to-right order.Inorder traversal with sorting
  10. 10Convert a normal BST into a Balanced BSTTurn a lopsided sorted tree into a bushy one with the same numbers, by putting the middle number on top again and again, or by folding a stick in half.Divide and conquer
  11. 11Merge two BSTCombine two sorted trees into one sorted line, and then into one balanced tree, by walking both trees in order at the same time and always taking the smaller front number.Inorder traversal with two stacksMust do
  12. 12Find Kth largest element in a BSTCount down through a sorted tree from the biggest number and stop at the k-th one, by mirroring the usual left-to-right walk.Reverse inorder traversal
  13. 13Find Kth smallest element in a BSTCount your way up through a sorted tree from the smallest number and stop at the k-th one, without writing the whole tree down.Inorder traversal
  14. 14Count pairs from 2 BST whose sum is equal to given value XCount pairs, one number from each of two sorted trees, that add up to x, by walking one tree from small to big and the other from big to small at the same time.Two pointers
  15. 15Find the median of BST in O(n) time and O(1) spaceFind the middle number of a sorted tree without any list or stack, by tying temporary ropes that let you climb back up and walking the tree in order twice.Morris traversal
  16. 16Count BST nodes that lie in a given rangeCount the numbers in a sorted tree that fall between a low and a high mark, skipping whole branches that are sure to be too small or too big.Depth first search with pruning
  17. 17Replace every element with the least greater element on its rightFor each number in a row, find the smallest bigger number somewhere to its right, by reading the row backwards into a sorted tree.BST insert with successor
  18. 18Given n appointments, find the conflicting appointmentsGo through appointments in order and say which earlier one each clashes with, using a sorted tree where every spot also remembers the latest finishing time below it.Interval tree
  19. 19Check preorder is valid or notDecide whether a list could be the top-first visiting order of a sorted tree, by remembering a floor that no later number may go below.Monotonic stack
  20. 20Check whether BST contains Dead endFind a leaf in a sorted tree of positive whole numbers where no new number could ever be hung below it, because both neighbors are already taken.Depth first search with bounds
  21. 21Largest BST in a Binary TreeFind the biggest piece of a messy tree that is a proper sorted tree, by letting every spot report its size, smallest and biggest number up to its parent.Postorder with return infoMust do
  22. 22Flatten BST to sorted listRewire a sorted tree into one straight sorted chain, reusing its own spots, by visiting them in order and hooking each one after the last.Inorder traversal
Next topicHeap