Runtime Complexity

lookup append insert delete

Space Complexity

Traversal

You process the following order in this way:

  • Pre-order: current node, left, right
  • In-order: left, current node, right
  • Post-order: left, right, current node

Binary Tree

Binary tree is a data structure where every node has at most two children, left and right node

A binary tree uses comparison to assign value, left child typically smaller than parent node, right node typically bigger than parent node

    1
   / \
  2   3

Binary Seach Tree

A BST is an ordered binary tree. So only in-order traversal makes sense. The first element in a a set is usually root.

    2
   / \
  1   3

Red-Black Tree

how to implement a red-black tree:

  1. new nodes are always red I. if parents are black, done II. if parents are red, i) if the uncle is red, big problem ii) if uncle is new or black A) if new node is outside - single rotation B) if new node is inside - double roation
  2. as you go down the tree, recolor the black with 2 red children to red with 2 black children

Degenerate Tree

A degenerate tree is an unbalanced tree which basically degrades to the performance of a linked list

Trie

Heap

Exercises

  • Implement a BST with insert and delete functions.
  • Print a tree using BFS and DFS.
  • Write a function that determines if a tree is a BST.
  • Find the smallest element in a BST.
  • Find the 2nd largest number in a BST.
  • Given a binary tree which is a sum tree (child nodes add to parent), write an algorithm to determine whether the tree is a valid sum tree.
  • Find the distance between 2 nodes in a BST and a normal binary tree.
  • Print the coordinates of every node in a binary tree, where root is 0,0.
  • Print a tree by levels.
  • Given a tree, verify that it contains a subtree.
  • Implement a binary min heap. Turn it into a binary max heap.
  • Find the max distance between 2 nodes in a BST.
  • Construct a BST given the pre-order and in-order traversal strings.