Trees 101: Binary, Heaps, Tries

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Today, we're going to learn all about trees, specifically binary search trees, heaps, and tries. We'll dive into how they work, and by the end of this blog you will be an expert on trees.

Tree Basics

A tree is a hierarchical data structure composed of nodes. It starts with a root node and branches out to child nodes.

Key Components

1. Root Node: The topmost node of the tree.
2. Child Nodes: Nodes directly connected to another node when moving away from the root.
3. Leaf Nodes: Nodes with no children.

Important Characteristics

• Trees cannot contain cycles.
• Nodes can store any data type.
• Parent links are optional.

Structure

• The root node has 0 or more child nodes.
• Each child node can have its own child nodes. This pattern continues, forming the tree structure.

Node/Tree Definition

Class-Based

class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }
}

class Tree {
  constructor(rootName) {
    this.root = new Node(rootName);
  }
}

Functional/Prototype-Based

function Node(name) {
  this.name = name;
  this.children = [];
}

function Tree(rootName) {
  this.root = new Node(rootName);
}

Binary Trees

A binary tree is a tree in which each node has up to 2 children. A binary search tree on the other hand is a binary tree in which every node fits a specific ordering property: all left descendants ≤ n ≤ all right descendants. This is true for each node n.

Note: There are other BST definitions that don’t allow duplicate values.

Balanced vs. Unbalanced Trees

A balanced tree is a tree where the height of the left and right subtrees of every node differs by at most one. This property ensures that operations like insertion, deletion, and search have a time complexity of O(log n) in the average and worst cases.

Unbalanced trees, on the other hand, can degenerate into linear structures, potentially leading to O(n) time complexity for these operations.

Complete Binary Trees

Every level of the tree is filled, except for perhaps the last level. For the last level, it must be filled left to right.

Full Binary Trees

Every node has either 0 or 2 children. No nodes have only one child.

Perfect Binary Trees

One that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum # of nodes. It has exactly $2^k - 1$ nodes.

Binary Tree Traversal

When working with binary trees, we often need to visit all the nodes in a specific order. This process is called traversal.

In-Order Traversal

In-order traversal is like reading a book from left to right. Here's how it works:

1. Visit the left subtree.
2. Visit the root node.
3. Visit the right subtree.

This process is applied recursively to each subtree. When performed on a binary search tree, it visits the nodes in ascending order.

function inOrderTraversal(node) {
  if (node !== null) {
    inOrderTraversal(node.left);
    visit(node);
    inOrderTraversal(node.right);
  }
}

Pre-Order Traversal

In pre-order traversal, we follow this sequence:

1. Visit the root node first.
2. Traverse the left subtree.
3. Traverse the right subtree.

This "root-first" approach can be particularly useful in scenarios where you need to explore a tree's structure from the top down.

function preOrderTraversal(node) {
  if (node !== null) {
    visit(node); // root is first node visited
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
  }
}

Post-Order Traversal

In post-order traversal, we follow this sequence:

1. Traverse the left subtree
2. Traverse the right subtree
3. Visit the root node

This "bottom-up" approach visits all the children before their parent nodes.

function postOrderTraversal(node) {
  if (node !== null) {
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    visit(node); // root is last node visited
  }
}

Binary Heaps (Min-Heaps/Max-Heaps)

A min-heap is a complete binary tree where each node is smaller than its children. Thus, the root is the minimum element.

Key Operations

insert - start by inserting the element at the bottom. We insert at the rightmost spot so as to maintain the complete tree property. Then, we fix the tree by swapping the new element with its parent, until we find an appropriate spot for the element (bubbling up the minimum element). This takes $O(logn)$ time, where n is the number of nodes in the heap.

extract_min - finding the minimum element is easy. Removing it is tricky. First, remove the minimum element and swap it with the last element in the heap. Then, we bubble down this element, swapping it with one of its children (the smaller valued node) until the min-heap property is restored. This also takes $O(logn)$ time.

Max-heaps are essentially equivalent, but the elements are in descending order rather than ascending order.

Tries (Prefix Trees)

A trie is a variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word.

When building a trie for storing words, we need a way to mark the end of complete words. This is crucial for distinguishing between prefixes and actual words in the trie. There are two common approaches to implement this feature:

Special Terminating Node

Create a TerminatingTrieNode class that inherits from TrieNode. Use these special nodes to mark the end of a word

• Example: In a trie containing "man" and "many", the path to "man" ends with a terminating node, while "many" continues with regular nodes

Boolean Flag in Parent Node

Add a terminates boolean flag to each TrieNode. Set this flag to true for nodes that represent the last character of a word

• Example: For "man" and "many", the 'n' node would have terminates = true, while also having a child 'y' node

Both methods effectively distinguish between prefixes and complete words, allowing the trie to accurately store and retrieve words. The choice between these approaches often depends on specific implementation requirements and personal preference.

Use Case

A trie is typically used to store the entire English language for quick prefix lookups. While a HashMap can tell us whether a string is a valid word, it cannot tell us if a string is a prefix of any valid words. It takes $O(k)$ where k is length of string, to check if string is valid prefix.

Hope you enjoyed this blog :). Would love to hear feedback on other topics you would like to read about.