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
- Root Node: The topmost node of the tree.
- Child Nodes: Nodes directly connected to another node when moving away from the root.
- 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 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:
- Visit the left subtree.
- Visit the root node.
- 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:
- Visit the root node first.
- Traverse the left subtree.
- 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:
- Traverse the left subtree
- Traverse the right subtree
- 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 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 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 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.
Top comments (0)