Trees

Author: Jacob Park

A tree is a connected acyclic graph that consists of $n$ nodes and $n - 1$ edges.

  • Degree: The number of children of a node $x$ in a rooted tree $T$.
  • Depth: The length of the simple path from the root $r$ to a node $x$.
  • Height: The number of edges on the longest simple downward path from the node to a leaf. The height of a tree is the height of its root.

Binary Search Tree

Implementation of Node

In [1]:
package trees.binary_search_tree;

public class BinarySearchTreeNode {

    private int key;
    private int value;
    private BinarySearchTreeNode parent;
    private BinarySearchTreeNode left;
    private BinarySearchTreeNode right;

    public BinarySearchTreeNode(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public BinarySearchTreeNode getParent() {
        return parent;
    }

    public void setParent(BinarySearchTreeNode parent) {
        this.parent = parent;
    }

    public BinarySearchTreeNode getLeft() {
        return left;
    }

    public void setLeft(BinarySearchTreeNode left) {
        this.left = left;
    }

    public BinarySearchTreeNode getRight() {
        return right;
    }

    public void setRight(BinarySearchTreeNode right) {
        this.right = right;
    }

}
Out[1]:
trees.binary_search_tree.BinarySearchTreeNode

Implementation of Pre-Order Traversal

In [2]:
package trees.binary_search_tree;

import java.util.function.*;

public interface PreOrderTraversal {
    
    public default void preOrderTraversal(
            BinarySearchTreeNode node,
            BiConsumer<Integer, Integer> action) {
        if (node == null) {
            return;
        }
        action.accept(node.getKey(), node.getValue());
        preOrderTraversal(node.getLeft(), action);
        preOrderTraversal(node.getRight(), action);
    }
    
}
Out[2]:
trees.binary_search_tree.PreOrderTraversal

Implementation of In-Order Traversal

In [3]:
package trees.binary_search_tree;

import java.util.function.*;

public interface InOrderTraversal {
    
    public default void inOrderTraversal(
            BinarySearchTreeNode node,
            BiConsumer<Integer, Integer> action) {
        if (node == null) {
            return;
        }
        inOrderTraversal(node.getLeft(), action);
        action.accept(node.getKey(), node.getValue());
        inOrderTraversal(node.getRight(), action);
    }
    
}
Out[3]:
trees.binary_search_tree.InOrderTraversal

Implementation of Post-Order Traversal

In [4]:
package trees.binary_search_tree;

import java.util.function.*;

public interface PostOrderTraversal {
    
    public default void postOrderTraversal(
            BinarySearchTreeNode node,
            BiConsumer<Integer, Integer> action) {
        if (node == null) {
            return;
        }
        postOrderTraversal(node.getLeft(), action);
        postOrderTraversal(node.getRight(), action);
        action.accept(node.getKey(), node.getValue());
    }
    
}
Out[4]:
trees.binary_search_tree.PostOrderTraversal

Implementation of Morris Traversal (Threaded In-Order Traversal)

In [5]:
package trees.binary_search_tree;

import java.util.function.*;

public interface ForwardMorrisTraversal {
    
    public default void forwardMorrisTraversal(
            BinarySearchTreeNode node, 
            BiConsumer<Integer, Integer> action) {
        // Forward In-Order Traversal: Left, Visit, Right, Left,....
        // Threading: Given a node, its predecessor's right child should thread to the
        //            node.
        // Space: O(1) and No Parent References.
        while (node != null) {
            if (node.getLeft() == null) {
                // Case 1: Iteratively Equivalent to Recursive Exhaustion of Left. 
                // Visit:
                action.accept(node.getKey(), node.getValue());
                // Right:
                node = node.getRight();
            } else {
                // Case 2:
                // A. Find Predecessor to Thread:
                // Note 1: If the left child exists, then the predecessor is the
                //         maximum/rightmost leaf of the left subtree.
                // Note 2: If the candidate predecessor's right child already points to
                //         the node, then we have already threaded.
                BinarySearchTreeNode predecessorNode = node.getLeft();
                while (predecessorNode.getRight() != null &&
                       predecessorNode.getRight() != node) {
                    predecessorNode = predecessorNode.getRight();
                }
                // B. Thread Predecessor to Node:
                if (predecessorNode.getRight() == null) {
                    // Right:
                    predecessorNode.setRight(node);
                    // Left:
                    node = node.getLeft();
                }
                // C. Consume Thread to Successor:
                else {
                    // Consume Thread:
                    predecessorNode.setRight(null);
                    // Visit:
                    action.accept(node.getKey(), node.getValue());
                    // Right:
                    node = node.getRight();
                }
            }
        }
    }
    
}
Out[5]:
trees.binary_search_tree.ForwardMorrisTraversal
In [6]:
package trees.binary_search_tree;

import java.util.function.*;

public interface BackwardMorrisTraversal {
    
    public default void backwardMorrisTraversal(
            BinarySearchTreeNode node,
            BiConsumer<Integer, Integer> action) {
        // Backward In-Order Traversal: Right, Visit, Left, Right,....
        // Threading: Given a node, its successor's left child should thread to the
        //            node.
        // Space: O(1) and No Parent References.
        while (node != null) {
            if (node.getRight() == null) {
                // Case 1: Iteratively Equivalent to Recursive Exhaustion of Right. 
                // Visit:
                action.accept(node.getKey(), node.getValue());
                // Left:
                node = node.getLeft();
            } else {
                // Case 2:
                // A. Find Successor to Thread:
                // Note 1: If the right child exists, then the successor is the
                //         minimum/leftmost leaf of the right subtree.
                // Note 2: If the candidate successor's left child already points to
                //         the node, then we have already threaded.
                BinarySearchTreeNode successorNode = node.getRight();
                while (successorNode.getLeft() != null &&
                       successorNode.getLeft() != node) {
                    successorNode = successorNode.getLeft();
                }
                // B. Thread Predecessor to Node:
                if (successorNode.getLeft() == null) {
                    // Left:
                    successorNode.setLeft(node);
                    // Right:
                    node = node.getRight();
                }
                // C. Consume Thread to Predecessor:
                else {
                    // Consume Thread:
                    successorNode.setLeft(null);
                    // Visit:
                    action.accept(node.getKey(), node.getValue());
                    // Left:
                    node = node.getLeft();
                }
            }
        }
    }
    
}
Out[6]:
trees.binary_search_tree.BackwardMorrisTraversal
In [7]:
package trees.binary_search_tree;

import java.util.*;

public interface Search {
    
    public default BinarySearchTreeNode searchNode(
            BinarySearchTreeNode node,
            int key) {
        if (node == null) {
            throw new NoSuchElementException();
        }
        if (key == node.getKey()) {
            return node;
        }
        if (key < node.getKey()) {
            return searchNode(node.getLeft(), key);
        } else {
            return searchNode(node.getRight(), key);
        }
    }
    
}
Out[7]:
trees.binary_search_tree.Search

Implementation of Minimum

In [8]:
package trees.binary_search_tree;

import java.util.*;

public interface Minimum {
    
    public default BinarySearchTreeNode minimumNode(BinarySearchTreeNode node) {
        if (node == null) {
            throw new NoSuchElementException();
        }
        while (node.getLeft() != null) {
            node = node.getLeft();
        }
        return node;
    }
    
}
Out[8]:
trees.binary_search_tree.Minimum

Implementation of Maximum

In [9]:
package trees.binary_search_tree;

import java.util.*;

public interface Maximum {
    
    public default BinarySearchTreeNode maximumNode(BinarySearchTreeNode node) {
        if (node == null) {
            throw new NoSuchElementException();
        }
        while (node.getRight() != null) {
            node = node.getRight();
        }
        return node;
    }
    
}
Out[9]:
trees.binary_search_tree.Maximum

Implementation of Successor

In [10]:
package trees.binary_search_tree;

import java.util.*;

public interface Successor extends Minimum {
    
    public default BinarySearchTreeNode successorNode(BinarySearchTreeNode node) {
        if (node == null) {
            throw new NoSuchElementException();
        }
        if (node.getRight() != null) {
            return minimumNode(node.getRight());
        }
        BinarySearchTreeNode parentNode = node.getParent();
        BinarySearchTreeNode currentNode = node;
        while (parentNode != null && currentNode == parentNode.getRight()) {
            currentNode = parentNode;
            parentNode = parentNode.getParent();
        }
        return parentNode;
    }
    
}
Out[10]:
trees.binary_search_tree.Successor

Implementation of Predecessor

In [11]:
package trees.binary_search_tree;

import java.util.*;

public interface Predecessor extends Maximum {
    
    public default BinarySearchTreeNode predecessorNode(BinarySearchTreeNode node) {
        if (node == null) {
            throw new NoSuchElementException();
        }
        if (node.getLeft() != null) {
            return maximumNode(node.getLeft());
        }
        BinarySearchTreeNode parentNode = node.getParent();
        BinarySearchTreeNode currentNode = node;
        while (parentNode != null && currentNode == parentNode.getLeft()) {
            currentNode = parentNode;
            parentNode = parentNode.getParent();
        }
        return parentNode;
    }
    
}
Out[11]:
trees.binary_search_tree.Predecessor

Implementation of Insert

In [12]:
package trees.binary_search_tree;

import java.util.*;

public interface Insert {
    
    public default BinarySearchTreeNode insertNode(
            BinarySearchTreeNode rootNode,
            int key,
            int value) {
        if (rootNode == null) {
            return new BinarySearchTreeNode(key, value);
        }
        if (key < rootNode.getKey()) {
            rootNode.setLeft(insertNode(rootNode.getLeft(), key, value));
            rootNode.getLeft().setParent(rootNode);
        } else {
            rootNode.setRight(insertNode(rootNode.getRight(), key, value));
            rootNode.getRight().setParent(rootNode);
        }
        return rootNode;
    }
    
}
Out[12]:
trees.binary_search_tree.Insert

Implementation of Delete

In [13]:
package trees.binary_search_tree;

import java.util.*;

public interface Delete extends Minimum {
    
    public default BinarySearchTreeNode deleteNode(
            BinarySearchTreeNode rootNode,
            int key) {
        if (rootNode == null) {
            throw new NoSuchElementException();
        }
        if (key < rootNode.getKey()) {
            rootNode.setLeft(deleteNode(rootNode.getLeft(), key));
            if (rootNode.getLeft() != null) {
                rootNode.getLeft().setParent(rootNode);
            }
            return rootNode;
        } else if (key > rootNode.getKey()) {
            rootNode.setRight(deleteNode(rootNode.getRight(), key));
            if (rootNode.getRight() != null) {
                rootNode.getRight().setParent(rootNode);
            }
            return rootNode;
        } else {
            if (rootNode.getLeft() == null && rootNode.getRight() == null) {
                // Case 1: No Children / Leaf Node => Delete Self.
                return null;
            } else if (rootNode.getLeft() == null) {
                // Case 2a: One Right Child => Replace Self with Right Child.
                return rootNode.getRight();
            } else if (rootNode.getRight() == null) {
                // Case 2b: One Left Child => Replace Self with Left Child.
                return rootNode.getLeft();
            } else {
                // Case 3: Two Children => Replace Self with Successor.
                final BinarySearchTreeNode successorNode =
                    minimumNode(rootNode.getRight());
                rootNode.setKey(successorNode.getKey());
                rootNode.setValue(successorNode.getValue());
                rootNode.setRight(deleteNode(rootNode.getRight(), rootNode.getKey()));
                if (rootNode.getRight() != null) {
                    rootNode.getRight().setParent(rootNode);
                }
                return rootNode;
            }
        }
    }
    
}
Out[13]:
trees.binary_search_tree.Delete

Implementation of Merge Disjoint

In [14]:
package trees.binary_search_tree;

import java.util.*;

public interface MergeDisjoint extends Minimum, Maximum, Delete {
    
    public default BinarySearchTreeNode mergeDisjointNodes(
            BinarySearchTreeNode leftNode,
            BinarySearchTreeNode rightNode) {
        if (leftNode == null && rightNode == null) {
            return null;
        } else if (leftNode == null) {
            return rightNode;
        } else if (rightNode == null) {
            return leftNode;
        } else {
            // Assert Left <<< Right
            final BinarySearchTreeNode leftMaximum = maximumNode(leftNode);
            final BinarySearchTreeNode rightMinimum = minimumNode(rightNode);
            if (leftMaximum.getKey() > rightMinimum.getKey()) {
                throw new IllegalStateException();
            }
            deleteNode(leftNode, leftMaximum.getKey());
            final BinarySearchTreeNode rootNode =
                new BinarySearchTreeNode(leftMaximum.getKey(), leftMaximum.getValue());
            rootNode.setLeft(leftNode);
            rootNode.setRight(rightNode);
            return rootNode;
        }
    }
    
}
Out[14]:
trees.binary_search_tree.MergeDisjoint

Implementation of Binary Search Tree

In [15]:
package trees.binary_search_tree;

import java.util.*;
import java.util.function.*;

public class BinarySearchTree implements 
    PreOrderTraversal, 
    InOrderTraversal, 
    PostOrderTraversal, 
    ForwardMorrisTraversal, 
    BackwardMorrisTraversal, 
    Search, 
    Minimum, 
    Maximum, 
    Successor, 
    Predecessor, 
    Insert, 
    Delete,
    MergeDisjoint {

    private BinarySearchTreeNode root;

    public BinarySearchTree() { }

    public void preOrderTraversal(BiConsumer<Integer, Integer> action) {
        preOrderTraversal(root, action);
    }

    public void inOrderTraversal(BiConsumer<Integer, Integer> action) {
        inOrderTraversal(root, action);
    }

    public void postOrderTraversal(BiConsumer<Integer, Integer> action) {
        postOrderTraversal(root, action);
    }

    public void forwardMorrisTraversal(BiConsumer<Integer, Integer> action) {
        forwardMorrisTraversal(root, action);
    }

    public void backwardMorrisTraversal(BiConsumer<Integer, Integer> action) {
        backwardMorrisTraversal(root, action);
    }

    public int searchValue(int key) {
        return searchNode(root, key).getValue();
    }

    public int minimumValue() {
        return minimumNode(root).getValue();
    }

    public int maximumValue() {
        return maximumNode(root).getValue();
    }

    public int successorKey(int key) {
        final BinarySearchTreeNode resultNode = successorNode(searchNode(root, key));
        if (resultNode == null) {
            throw new NoSuchElementException();
        }
        return resultNode.getKey();
    }

    public int predecessorKey(int key) {
        final BinarySearchTreeNode resultNode = predecessorNode(searchNode(root, key));
        if (resultNode == null) {
            throw new NoSuchElementException();
        }
        return resultNode.getKey();
    }

    public void insert(int key, int value) {
        root = insertNode(root, key, value);
    }

    public void delete(int key) {
        deleteNode(root, key);
    }

}
Out[15]:
trees.binary_search_tree.BinarySearchTree
In [16]:
package trees.binary_search_tree;

final BinarySearchTree tree = new BinarySearchTree();

tree.insert(50, 50);
tree.insert(30, 30);
tree.insert(20, 20);
tree.insert(40, 40);
tree.insert(70, 70);
tree.insert(60, 60);
tree.insert(80, 80);

System.out.print("Pre-Order Traversal: ");
tree.preOrderTraversal((k,v) -> System.out.print(String.format("%d,", k)));
System.out.println("Nil");

System.out.print("In-Order Traversal: ");
tree.inOrderTraversal((k,v) -> System.out.print(String.format("%d,", k)));
System.out.println("Nil");

System.out.print("Post-Order Traversal: ");
tree.postOrderTraversal((k,v) -> System.out.print(String.format("%d,", k)));
System.out.println("Nil");

System.out.print("Forward Morris Traversal: ");
tree.forwardMorrisTraversal((k,v) -> System.out.print(String.format("%d,", k)));
System.out.println("Nil");

System.out.print("Backward Morris Traversal: ");
tree.backwardMorrisTraversal((k,v) -> System.out.print(String.format("%d,", k)));
System.out.println("Nil");

System.out.println(String.format("Search Value 40: %d", tree.searchValue(40)));

System.out.println(String.format("Minimum Value: %d", tree.minimumValue()));

System.out.println(String.format("Maximum Value: %d", tree.maximumValue()));

System.out.println(String.format("Successor Key 40: %d", tree.successorKey(40)));

System.out.println(String.format("Predecessor Key 40: %d", tree.predecessorKey(40)));

System.out.print("Delete Key 20: ");
tree.delete(20);
tree.preOrderTraversal((k,v) -> System.out.print(String.format("%d,", k)));
System.out.println("Nil");

System.out.print("Delete Key 30: ");
tree.delete(30);
tree.preOrderTraversal((k,v) -> System.out.print(String.format("%d,", k)));
System.out.println("Nil");

System.out.print("Delete Key 50: ");
tree.delete(50);
tree.preOrderTraversal((k,v) -> System.out.print(String.format("%d,", k)));
System.out.println("Nil");

Pre-Order Traversal: 50,30,20,40,70,60,80,Nil
In-Order Traversal: 20,30,40,50,60,70,80,Nil
Post-Order Traversal: 20,40,30,60,80,70,50,Nil
Forward Morris Traversal: 20,30,40,50,60,70,80,Nil
Backward Morris Traversal: 80,70,60,50,40,30,20,Nil
Search Value 40: 40
Minimum Value: 20
Maximum Value: 80
Successor Key 40: 50
Predecessor Key 40: 30
Delete Key 20: 50,30,40,70,60,80,Nil
Delete Key 30: 50,40,70,60,80,Nil
Delete Key 50: 60,40,70,80,Nil
Out[16]:
null

Fenwick Tree (Cumulative Queries)

See Link.

  • A Fenwick Tree (or a Binary Indexed Tree) is used to answer cumulative queries about a data set.
  • In a Fenwick Tree, each position is responsible for storing the cumulative summary of Integer.lowestOneBit(position) number of previous positions.

It is represented by a 1-indexed array.

In [17]:
package trees.fenwick_tree;

public class FenwickTree {

    private final int[] array;

    public FenwickTree(int length) {
        this.array = new int[length + 1];
    }

    public void add(int index, int value) {
        int position = index + 1;
        while (position < array.length) {
            array[position] += value;
            position += Integer.lowestOneBit(position);
        }
    }

    public int sum(int index) {
        int position = index + 1;
        int sum = 0;
        while (position > 0) {
            sum += array[position];
            position -= Integer.lowestOneBit(position);
        }
        return sum;
    }

}
Out[17]:
trees.fenwick_tree.FenwickTree
In [18]:
package trees.fenwick_tree;

final int[] array = new int[] {1, 2, 3, 4, 5, 6, 7, 8};

final FenwickTree tree = new FenwickTree(array.length);

for (int index = 0; index < array.length; index++) {
    tree.add(index, array[index]);
}

System.out.println(String.format("Sum to Index 0: %d", tree.sum(0)));
System.out.println(String.format("Sum to Index 1: %d", tree.sum(1)));
System.out.println(String.format("Sum to Index 2: %d", tree.sum(2)));
System.out.println(String.format("Sum to Index 3: %d", tree.sum(3)));
System.out.println(String.format("Sum to Index 4: %d", tree.sum(4)));
System.out.println(String.format("Sum to Index 5: %d", tree.sum(5)));
System.out.println(String.format("Sum to Index 6: %d", tree.sum(6)));
System.out.println(String.format("Sum to Index 7: %d", tree.sum(7)));

Sum to Index 0: 1
Sum to Index 1: 3
Sum to Index 2: 6
Sum to Index 3: 10
Sum to Index 4: 15
Sum to Index 5: 21
Sum to Index 6: 28
Sum to Index 7: 36
Out[18]:
null

Segment Tree (Range Queries)

See Link.

  • A Segment Tree is used to answer range queries about a data set.
  • A Segment Tree is structured like a binary heap such that parent nodes store the cummulative summary of their children.
  • The leaves are the original values. Thus, an array of size $2n$ is sufficient to construct a Segment Tree. In this construction, index 1 represents the root while indices $n$ to $2n-1$ represent the original values.

It is represented by a 0-indexed array.

In [19]:
package trees.segment_tree;

import java.util.*;

public class SegmentTree {
    
    private final int[] array;
    private final int length;

    public SegmentTree(int length) {
        this.array = new int[2 * length];
        this.length = length;
    }

    public void add(int index, int value) {
        final int leafIndex = length + index;
        array[leafIndex] += value;
        for (int parentIndex = leafIndex / 2; parentIndex >= 1; parentIndex /= 2) {
            final int leftChildIndex = 2 * parentIndex;
            final int rightChildIndex = 2 * parentIndex + 1;
            array[parentIndex] = array[leftChildIndex] + array[rightChildIndex];
        }
    }

    public int sum(int fromIndex, int toIndex) {
        int fromLeafIndex = length + fromIndex;
        int toLeafIndex = length + toIndex;
        int sum = 0;
        while (fromLeafIndex <= toLeafIndex) {
            if (fromLeafIndex % 2 == 1) {
                sum += array[fromLeafIndex++];
            }
            if (toLeafIndex % 2 == 0) {
                sum += array[toLeafIndex--];
            }
            fromLeafIndex /= 2;
            toLeafIndex /= 2;
        }
        return sum;
    }

}
Out[19]:
trees.segment_tree.SegmentTree
In [20]:
package trees.segment_tree;

final int[] array = new int[] {1, 2, 3, 4, 5, 6, 7, 8};

final SegmentTree tree = new SegmentTree(array.length);

for (int index = 0; index < array.length; index++) {
    tree.add(index, array[index]);
}

System.out.println(String.format("Sum from Index 0 to Index 0: %d", tree.sum(0, 0)));
System.out.println(String.format("Sum from Index 0 to Index 3: %d", tree.sum(0, 3)));
System.out.println(String.format("Sum from Index 4 to Index 7: %d", tree.sum(4, 7)));
System.out.println(String.format("Sum from Index 0 to Index 7: %d", tree.sum(0, 7)));

Sum from Index 0 to Index 0: 1
Sum from Index 0 to Index 3: 10
Sum from Index 4 to Index 7: 26
Sum from Index 0 to Index 7: 36
Out[20]:
null

Tournament Tree (Merge Heap) ($O(n\log(k))$)

See Link.

  • A Tournament Tree is used to merge a set of sorted iterators into a single sorted iterator.
  • A Winner Tree is structured like a binary heap such that parent nodes store the lesser key of their children.
  • The leaves are the heads of each sorted iterator.
In [21]:
package trees.tournament;

import java.util.*;

public class WinnerTree implements Iterator<Integer> {

    private final PriorityQueue<Leaf> winnerTree;

    public WinnerTree(List<Iterator<Integer>> iterators) {
        this.winnerTree = new PriorityQueue<>();
        for (Iterator<Integer> iterator : iterators) {
            final Leaf leaf = new Leaf(iterator);
            if (leaf.isEmpty()) {
                continue;
            }
            this.winnerTree.offer(leaf);
        }
    }

    @Override
    public boolean hasNext() {
        return !winnerTree.isEmpty();
    }

    @Override
    public Integer next() {
        if (winnerTree.isEmpty()) {
            throw new NoSuchElementException();
        }
        final Leaf winnerLeaf = winnerTree.poll();
        final int winnerValue = winnerLeaf.poll();
        if (!winnerLeaf.isEmpty()) {
            winnerTree.offer(winnerLeaf);
        }
        return winnerValue;
    }

    private static class Leaf implements Comparable<Leaf> {

        private final Iterator<Integer> iterator;
        private Integer head;

        public Leaf(Iterator<Integer> iterator) {
            this.iterator = iterator;
            this.head = iterator.hasNext() ? iterator.next() : null;
        }

        public Integer peek() {
            if (head == null) {
                throw new NoSuchElementException();
            }
            return head;
        }

        public Integer poll() {
            final Integer currentHead = head;
            head = iterator.hasNext() ? iterator.next() : null;
            return currentHead;
        }

        public boolean isEmpty() {
            return head == null;
        }

        @Override
        public int compareTo(Leaf that) {
            return Integer.compare(this.peek(), that.peek());
        }

    }

}
Out[21]:
trees.tournament.WinnerTree
In [22]:
package trees.tournament;

import java.util.*;

final WinnerTree winnerTree = new WinnerTree(Arrays.asList(
    Arrays.asList(2, 5, 7, 9, 10).iterator(),
    Arrays.asList(1, 3, 4).iterator(),
    Arrays.asList(6, 8).iterator()
));

winnerTree.forEachRemaining(k -> System.out.print(String.format("%d,", k)));
System.out.println("Nil");

1,2,3,4,5,6,7,8,9,10,Nil
Out[22]:
null

Trie (String Queries)

See Link.

  • A Trie (or a Prefix Tree) is a rooted tree that maintains a set of strings.
  • Each string is stored as a character chain that starts at the root node.
  • If two strings have a common prefix, they also have a common chain in the tree.
In [23]:
package trees.trie;

import java.util.*;

public class Trie {

    private static class TrieNode {

        private final Map<Character, TrieNode> children;
        private boolean isString;

        public TrieNode() {
            this.children = new HashMap<>();
            this.isString = false;
        }

    }

    private final TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode currentNode = root;
        for (final char character : word.toCharArray()) {
            final Map<Character, TrieNode> children = currentNode.children;
            if (!children.containsKey(character)) {
                children.put(character, new TrieNode());
            }
            currentNode = children.get(character);
        }
        currentNode.isString = true;
    }

    public boolean search(String word) {
        final TrieNode terminalNode = find(word);
        return terminalNode != null && terminalNode.isString;
    }

    public boolean startsWith(String prefix) {
        final TrieNode terminalNode = find(prefix);
        return terminalNode != null;
    }
    
    private TrieNode find(String prefix) {
        TrieNode currentNode = root;
        for (final char character : prefix.toCharArray()) {
            final Map<Character, TrieNode> children = currentNode.children;
            if (!children.containsKey(character)) {
                return null;
            }
            currentNode = children.get(character);
        }
        return currentNode;
    }

}
Out[23]:
trees.trie.Trie
In [24]:
package trees.trie;

final Trie trie = new Trie();

trie.insert("CANAL");
trie.insert("CANDY");

System.out.println(String.format("Search(CANAL): %b", trie.search("CANAL")));
System.out.println(String.format("Search(CANDY): %b", trie.search("CANDY")));
System.out.println(String.format("Search(CANON): %b", trie.search("CANON")));
System.out.println(String.format("StartsWith(CAN): %b", trie.startsWith("CAN")));

Search(CANAL): true
Search(CANDY): true
Search(CANON): false
StartsWith(CAN): true
Out[24]:
null