Table of Contents

Description

• A tree is a type of graph that has no closed loops.
• It’s composed of:
  • Nodes.
    • Each node is an object spawned from a Node class.
    • It can contain any primitive, data type or object.
  • The starting node at the top of the tree is the root.
  • Each node is connected to 0 or more nodes by branches.

Types of Trees

Hierarchy

• Binary Tree
  • Binary Search Tree
  • Complete Binary Tree
    • Binary Heap
      • Min-Heap
      • Max-Heap
  • Full Binary Tree
  • Perfect Binary Tree
• Balanced Tree
  • Red-Black Tree
  • AVL Tree
• Trie (Prefix Tree)

Tree Variants

Ignore degenerate trees

• Binary Tree: A tree where every node has at max 2 children.
  • A node can have 0 or 1 children, but not 3.
• Complete Binary Tree: A binary tree where
  1. Every level is filled (has the maximum possible number of nodes), except for maybe the bottom level.
  2. If the bottom level isn’t filled, it’s filled from left to right. The empty nodes have to be at the far right.
• Full Binary Tree: A binary tree where no node has only 1 child.
• Perfect Binary Tree: A binary tree where every level is completely filled
  • Every perfect binary tree has a predetermined number of nodes: N = 2L - 1
    • N = number of nodes in the tree.
    • L = number of levels in the tree.
• Balanced Tree: Any tree where the depth of the left and right side are mostly balanced; there can only be at most 1 level of depth more on one side.

Binary Search Tree

• A binary search tree is a subset of binary trees where the nodes are sorted from left to right.
  • Condition: ALL left descendants ≤ EACH NODE ≤ ALL right descendants
  • This means the left child and all of its descendants must be smaller. Same for the right child and its descendants being bigger.