Trees

• A rooted, directed, acyclic structure
• Properties
  • Rooted: One root
  • Directed: Each node has one parent
  • Acyclic: No cycles

Use Cases

• Decision trees
• File systems
• Expression trees
• Search trees

Terminology

• Root: The node at the top
• Edge: Connection between two nodes
• Relationships
  • Children: Successors of a node
  • Parent: Predecessor of a node
  • Grandparent: Predecessor of a node’s parent
  • Siblings: Nodes that have the same parent
  • Cousins: Nodes that share the same grandparent
• Ancestor: Nodes that can be reached by moving only upwards from a node
• Descendent: Nodes that can be reached by moving only downwards from a node
• Leaf: Node with no children
• Subtree: Tree whose root is a child of a node
• Level (Depth): Number of edges between a node and the root
• Height of Node: Length of longest path from the node to a leaf
• Height of Tree: The height of the root node
  • can be either 0 based or 1 based (if the root is counted in the total or not)

Types

• N-Ary Tree
  • A tree with each node consisting of at most n children
  • Max total nodes: $N=\frac{n^h-1}{n-1}$
• Binary Tree
• Balanced Trees

Tree Representation

Array

• Since we know every node with contain at most n children, we can allocate that much for each level and have blank spots for missing nodes
• Each node (and missing node) gets assigned an index going top down from left to right on every level
  • Provides random access of nodes
• Unbalanced trees waste a lot of memory → Only really good for perfect or complete binary trees
• Indexes for binary tree
  • Parent: $\frac{1}{2}(i-1)$
  • Left child: $2i+1$
  • Right child: $2i+2$

Linked List

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};