How to implement a tree data-structure in Java?

java

data-structure

tree-traversal

performance-optimization

byAlex Kataev·Jan 2, 2025

Setting up a basic Tree or Graph structure in Java is straightforward thanks to a TreeNode class, which should contain data and hold a list of further TreeNode objects, or children. Leveraging generics grants us a dynamic, flexible solution.

class TreeNode<T> {
    T data; // Could be anything! your wish 😉
    List<TreeNode<T>> children = new ArrayList<>(); // Ah! The joy of kids

    // Data in; node's out!
    TreeNode(T data) { this.data = data; }

    // Believe in 'propagation'. Add a child node
    void addChild(TreeNode<T> child) { children.add(child); }

    // Having second thoughts? Remove a child node
    boolean removeChild(TreeNode<T> child) { return children.remove(child); }

    // Deep dive into the rabbit hole (node's children)
    List<TreeNode<T>> getChildren() { return children; } 
}

// Now to Build some real-world stuff
TreeNode<String> root = new TreeNode<>("root");
TreeNode<String> child1 = new TreeNode<>("child1");
TreeNode<String> child2 = new TreeNode<>("child2");

// The childNodes have found a home 😂
root.addChild(child1);
root.addChild(child2);

With minimum code fluff, we get a no-nonsense, essential tree structure capable of adding and removing nodes on the fly. Isn't recursion a beaut!

Tailored Needs? Easy Breezy

Float like a butterfly, sting like a bee. When your requirements are very specific, tailor the tree structure to best fit your needs.

class StringTreeNode {
    String name;
    List<StringTreeNode> subordinates = new ArrayList<>();

    StringTreeNode(String name) { this.name = name; }
    void addSubordinate(String name) { subordinates.add(new StringTreeNode(name)); }
    List<StringTreeNode> getSubordinates() { return subordinates; }
}

Tailor your class to hold only specific data type and only necessary operations. Kinda feels like 'The kingsguard' of Prototypes, right!

Swoop and Sweep: The Art of Traversal

Going from root to leaves or vice-versa, traversal is an essential operation. Here are some traversal techniques:

Pre-order: Visit node, then its children. (Sunday mass, then brunch!)
In-order: Reserved for our binary tree, visit the left child, then node, then right child. (Sounds very monarchy)
Post-order: Visit the node's children, then node itself. (Desserts before main meal, unconventional!)
Level-order: Visit each node level by level. (Job promotions be like)

Power of Performance

Bulky trees (not looking at you, Redwoods 🌲) can cause performance slow-downs. Balance these Juggernauts by using a linked structure for sparse trees or an array-based approach for complete/nearly-complete trees.

Watch out for Pitfalls

Circular references: Like the Ouroboros, avoid adding a node as its own ancestor—lest you churn out infinite loops!
Mutability: If nodes contain mutable objects, ensure change propagation, else risk value inconsistency. The Heartbleed bug says Hi!

Advanced Breakdown

Swing TreeModel

Swinging into the world of GUI applications, javax.swing.tree gifts us with TreeModel and TreeNode, equipping ready-made structures sans UI attachment.

Libraries: Advanced Hacks Unleashed

Prowess increased with libraries like Apache Commons Collections. They provide sophisticated implementations to work that tree magic.

Custom Seekers (Iterators)

Digital tree hikers! Write a custom iterator inside TreeNode class for smoother tree traversal.

class TreeNode<T> implements Iterable<T> { 
    // Original TreeNode code...

    @Override
    public Iterator<T> iterator() {
        return new TreeIterator<>(this);
    }
    
    private static class TreeIterator<T> implements Iterator<T> {
        // Iterator's code...
    }
}