Forem: Knitely

Graphs In Java (Part 2)

Knitely — Fri, 04 Jul 2025 15:32:55 +0000

Introduction

Welcome back, graph enthusiasts, for the highly anticipated sequel to our last discussion. Get ready for some significant renovations to the code we wrote last time.

To guide you through this architectural marvel, we've introduced a special instruction: if a code snippet is wrapped with this ---- sign, it means that piece of code is being evicted! Simply remove it and then immediately install the brand-new, shiny code directly below it. That being said, follow my Telegram Channel and let's go to business.

Topological ordering

A topological ordering, or topological sort, is like trying to put your socks on before your shoes (unless you're a true rebel, but then you wouldn't need a topological sort). It's a linear ordering of the vertices in a directed acyclic graph (DAG), which basically means it's a list of things where there's no going in circles (because that would just be chaotic, like trying to tie your shoelaces before you've even picked out the shoes). For every directed edge (u, v), vertex u absolutely, positively must come before vertex v. In simpler terms, it's arranging your tasks so that all dependencies are respected. So, if task A must be completed before task B, then A will appear before B in the sorted list. Otherwise, you'd end up trying to eat dessert before dinner, and we all know how well that goes over with Mom. Look at the figure below for more understanding.

Alright, our definition is done and dusted! Now, let's make our lovely graph's topological ordering happen. Grab that GraphAlgorithms.java file from our last adventure, and go ahead and write the following code right in there.

public static <V> ArrayList<Vertex<V>> topologicalSort(Graph<V> graph) {
      ArrayList<Vertex<V>> topological = new ArrayList<>();
      Stack<Vertex<V>> stack = new Stack<>();

      HashMap<Vertex<V>, Integer> inCount = new HashMap<>();
      for (Vertex<V> v : graph.vertices()) {
          inCount.put(v, graph.inDegree(v));
          if (inCount.get(v) == 0) {
              stack.push(v);
          }
      }

      while (!stack.isEmpty()) {
          Vertex<V> current = stack.pop();
          topological.add(current);
          for (Vertex<V> vertex : graph.outgoingVertices(current)) {
              inCount.put(vertex, inCount.get(vertex) - 1);
              if (inCount.get(vertex) == 0) {
                  stack.push(vertex);
              }
          }
      }

      return topological;
  }

So, picture this: our HashMap is basically the graph's gossipy social network, listing every vertex and precisely how many 'friends' (incoming edges) they need to be introduced by. At first, our stack is super exclusive, only letting in the popular kids who have no dependencies—they just waltz right in! But here's the kicker: the more incoming edges a vertex has, the more demanding it is. It's like, 'Sorry, can't be processed until Tasks A, B, and C have cleared the path for me!' Talk about high-maintenance!

To see if the code actually, go on over to your Main.java file. Then, insert the following code snippet inside your main() method. This is where we'll create a graph that resembles the one in the figure below.

AdjacencyMapGraph<Integer> graph = new AdjacencyMapGraph<>(true);
Vertex<Integer> one = graph.insertVertex(1);
Vertex<Integer> two = graph.insertVertex(2);
Vertex<Integer> three = graph.insertVertex(3);
Vertex<Integer> four = graph.insertVertex(4);
Vertex<Integer> five = graph.insertVertex(5);

graph.insertEdge(one, two);
graph.insertEdge(one, three );
graph.insertEdge(one, five);
graph.insertEdge(two, three);
graph.insertEdge(three, four);
graph.insertEdge(three, five);
graph.insertEdge(four, five);

var topological = GraphAlgorithms.topologicalSort(graph);
for (Vertex<Integer> vertex : topological) {
    System.out.print(vertex.getElement() + ", "); // [1, 2, 3, 4, 5]
}

While the in-degree method (Kahn's algorithm) is fantastic, the Depth First Search (DFS) approach is another elegant and equally powerful way to achieve a topological ordering.

The core idea with DFS is indeed to push vertices onto a stack after all their dependencies (their outgoing edges) have been fully explored. When you're done, flipping that stack gives you the perfect, reverse-engineered chronological order. I'll leave the thrilling implementation of this particular sorcery to you.

Weighted Graphs

A weighted graph is just a regular graph that started dealing with real-world expenses. Each edge is assigned a numerical (and let me reiterate, numerical) value, known as a 'weight.' This weight could be a cost (like how much that cross-town taxi really hits your wallet), a distance (because some detours are just plain rude), or any other metric that says, 'Hey, this connection actually matters more (or less) than that one. We need to know if that connection is a quick hop or an epic quest.
Okay, so our edges now come with a bonus feature: weights. To incorporate this crucial information into our graph, we'll need to update our existing code. That means it's time to modify some elements from our last post to accurately represent these weighted connections. Go ahead and create an Edge.java file, then add the provided code.

import java.util.ArrayList;

public class Edge<V> {

    private Vertex<V> origin, destination;
    private int weight;

    public Edge(Vertex<V> origin, Vertex<V> destination, int weight) {
        this.origin = origin;
        this.destination = destination;
        this.weight = weight;
    }

    public int getWeight() {
        return weight;
    }

    public ArrayList<Vertex<V>> endpoints() {
        ArrayList<Vertex<V>> endpoints = new ArrayList<>(2);
        endpoints.add(origin);
        endpoints.add(destination);
        return endpoints;
    }

    public Vertex<V> opposite(Vertex<V> v) {
        if (v == origin)
            return destination;

        return origin;
    }

    public Vertex<V> getOrigin() {
        return origin;
    }

    public Vertex<V> getDestination() {
        return destination;
    }
}

Next go to Graph.java file and the following code in our interface.

    int outDegree(Vertex<V> v) throws IllegalArgumentException;
    int inDegree(Vertex<V> v) throws IllegalArgumentException;

    Iterable<Edge<V>> outgoingEdges(Vertex<V> v) throws IllegalArgumentException;
    Iterable<Edge<V>> incomingEdges(Vertex<V> v) throws IllegalArgumentException;

    Edge<V> getEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException;
}

With the new methods added to our interface, the next logical step—for obvious reasons—is to provide their implementation within our AdjacencyMapGraph class. This is where we'll define the functionality for those methods. Please insert the code below into your AdjacencyMapGraph class.


        // ------ snip ----
        @Override
        public Iterable<Vertex<V>> outgoingVertices(Vertex<V> v) throws IllegalArgumentException {
            InnerVertex<V> outgoing = validate(v);
            ---- return outgoing.getOutgoing(); ----
            return outgoing.getOutgoing().keySet();
        }

        @Override
        public Iterable<Vertex<V>> incomingVertices(Vertex<V> v) throws IllegalArgumentException {
            InnerVertex<V> incoming = validate(v);
            ---- return incoming.getIncoming(); ----
            return incoming.getIncoming().keySet();
        }

    @Override
    public Iterable<Edge<V>> outgoingEdges(Vertex<V> v) throws IllegalArgumentException {
        InnerVertex<V> incoming = validate(v);
        return incoming.getOutgoing().values();
    }

    @Override
    public Iterable<Edge<V>> incomingEdges(Vertex<V> v) throws IllegalArgumentException {
        InnerVertex<V> outgoing = validate(v);
        return outgoing.getIncoming().values();
    }

    @Override
    public Edge<V> getEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException {
        if (!isValidVertex(u) || !isValidVertex(v)) {
            throw new IllegalArgumentException("Invalid vertex");
        }

        if (hasEdge(u, v)) {
            InnerVertex<V> origin = validate(u);
            InnerVertex<V> destination = validate(v);
            return origin.getOutgoing().get(destination);
        }
        return null;
    }

}

Alright, it's time to get our InnerVertex class ready for the big leagues—where edges aren't just connections, they have weight. To make sure our vertices can properly keep track of these weighted relationships, we need to swap out that old HashSet for a more robust HashMap. This way, we can associate each connected vertex (our key) with its specific edge (our value).

So, head into your InnerVertex class and add the following code:

protected static class InnerVertex<V> implements Vertex<V> {
        // ---- snip ----
        ---- private HashSet<Vertex<V>> outgoing, incoming; ----
        private HashMap<Vertex<V>, Edge<V>> outgoing, incoming;

        public InnerVertex(V element, boolean isDirected) {
            this.element = element;
            ---- outgoing = new HashSet<>(); ----
            outgoing = new HashMap<>();
            if (isDirected) {
                    ---- incoming = new HashSet<>(); ----
                incoming = new HashMap<>();
            } else {
                incoming = outgoing;
            }
        }

        // ---- snip ----
        ---- 
        public HashSet<Vertex<V>> getOutgoing() throws IllegalArgumentException {
            return outgoing;
            } 
            ----
        public HashMap<Vertex<V>, Edge<V>> getOutgoing() throws IllegalArgumentException {
            return outgoing;
        }

        ----
        public HashSet<Vertex<V>> getIncoming() throws IllegalArgumentException {
            return incoming;
            } 
            ----
        public HashMap<Vertex<V>, Edge<V>> getIncoming() throws IllegalArgumentException {
            return incoming;
        }

        // ---- snip ----
    }

To clear up those red lines in your AdjacencyMapGraph class, go ahead and add the following code inside it. This should sort out any errors you're seeing in your text editor.

// ---- snip ----
---- private void removeEdge(HashSet<Vertex<V>> edges, Vertex<V> vertex, boolean isOutgoing) { ----
private void removeEdge(HashMap<Vertex<V>, Edge<V>> edges, Vertex<V> vertex, boolean isOutgoing) {
    for (Vertex<V> ve : edges.keySet()) {
        InnerVertex<V> vert = validate(ve);
        if (isOutgoing) {
            vert.getIncoming().remove(vertex);
        } else {
            vert.getOutgoing().remove(vertex);
        }

        numEdges--;
    }
    edges.clear();
}

// -- snip --
@Override
public V removeVertex(Vertex<V> v) throws IllegalArgumentException {
    // ---- snip ----

        ---- HashSet<Vertex<V>> outgoing = vertex.getOutgoing(); ----
    HashMap<Vertex<V>, Edge<V>> outgoing = vertex.getOutgoing();
    removeEdge(outgoing, vertex, true);

        ---- HashSet<Vertex<V>> incoming = vertex.getIncoming(); ----
    HashMap<Vertex<V>, Edge<V>> incoming = vertex.getIncoming();
    removeEdge(incoming, vertex, false);

        // ---- snip ----
    return temp;
}

// ---- snip ----
@Override
public void insertEdge(Vertex<V> u, Vertex<V> v, int wight) throws IllegalArgumentException {
    // ---- snip ----
    if (!hasEdge(u, v)) {
            InnerVertex<V> origin = validate(u);
        InnerVertex<V> destination = validate(v);
        Edge<V> edge = new Edge<>(origin, destination, wight);

                ---- origin.getOutgoing().add(destination); ----
        ---- destination.getIncoming().add(origin); ----
        origin.getOutgoing().put(destination, edge);
        destination.getIncoming().put(origin, edge);
        numEdges++;
    } else
        throw new IllegalArgumentException("Edge from u to v exists");
}

Dijkstra’s Algorithm

Dijkstra's algorithm a blessing designed for those moments when you absolutely, positively need to find the shortest path between two points in a tangled mess of connections.

This clever little method doesn't just guess; it meticulously explores the graph, like a highly organized detective with a clipboard. It keeps track of where it's been (the "visited nodes" list) and how far it is to everywhere else (the "distance table"). Then, it repeatedly updates its "best guess" for how to get to neighboring nodes until, voilà, it's figured out the shortest route to every single reachable spot. So, next time you're stuck in a labyrinth, just remember Dijkstra—it's probably already mapped the fastest way out!

Our algorithm uses a handy little HashMap to keep tabs on how far each vertex thinks it is from the starting line, and a 'cloud' (because 'set of visited nodes' just sounds too boring) for all the vertices that have already had their moment in the sun.

But the real MVP, the one we built a tiny shrine for, is our magnificent PriorityQueue.This unsung hero makes sure the vertex with the shortest distance always cuts to the front of the line.

Here's the lowdown: we start by stuffing our lovely PriorityQueue and our distance HashMap. If a vertex is the 'source,' we graciously grant it a distance of zero. Everyone else? Straight to 'maximum integer' distance – tough luck, chumps.

Then, it's a looping frenzy until our PriorityQueue is completely exhausted. In each round, we heroically pop the current 'shortest distance' champion. Then, we parade through its outgoing edges, doing some quick math. If we find a path (current distance + edge weight) that's shorter than what's currently in our distance HashMap , we update it and invite that lucky vertex to the PriorityQueue party. Because who doesn't love a good shortcut?

You've absorbed the wisdom; now, go ahead and paste the code below into your GraphAlgorithms class.

import java.util.PriorityQueue;
import java.util.Queue;

public class GraphAlgorithms {
// ----- snip -----
public static <V> HashMap<Vertex<V>, Integer> shortestPathLengths(Graph<V> graph, Vertex<V> source) {
      HashMap<Vertex<V>, Integer> distances = new HashMap<>();
      HashMap<Vertex<V>, Integer> cloud = new HashMap<>();

      Queue<Edge<V>> queue = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));

      for (Vertex<V> vertex : graph.vertices()) {
          if (vertex == source) {
              distances.put(vertex, 0);
              queue.offer(new Edge<>(source, null, 0));
          } else {
              distances.put(vertex, Integer.MAX_VALUE);
              queue.offer(new Edge<>(source, null, Integer.MAX_VALUE));
          }
      }
      int size = queue.size();
      int counter = 0;

      while (size > counter && !queue.isEmpty()) {
          Edge<V> currentEdge = queue.poll();
          Vertex<V> currentVertex = currentEdge.getOrigin();
          int distance = currentEdge.getWeight();

          cloud.put(currentVertex, distance);
          for (Edge<V> edge : graph.outgoingEdges(currentVertex)) {
              Vertex<V> vertex = edge.opposite(currentVertex);

              if (cloud.get(vertex) == null) {
                  int weight = edge.getWeight();
                  int d = distance + weight;

                  if (d < distances.get(vertex)) {
                      distances.put(vertex, d);
                      queue.offer(new Edge<>(vertex, null, distances.get(vertex)));
                  }
              }
          }
          counter++;
      }

      return cloud;
  }

  // ----- snip -----

Alright, let's build that graph and put our Dijkstra's algorithm to the ultimate test! You can see from the figure below that the shortest distance from vertex 0 to vertex 4 is 17. We'll set up the graph just like that, then run our code to confirm it. Head over to your main() method and drop in the following code.

AdjacencyMapGraph<Integer> graph = new AdjacencyMapGraph<>(false);

Vertex<Integer> zero = graph.insertVertex(0);
Vertex<Integer> one = graph.insertVertex(1);
Vertex<Integer> two = graph.insertVertex(2);
Vertex<Integer> three = graph.insertVertex(3);
Vertex<Integer> four = graph.insertVertex(4);
Vertex<Integer> five = graph.insertVertex(5);
Vertex<Integer> six = graph.insertVertex(6);

graph.insertEdge(zero, two, 6);
graph.insertEdge(zero, one, 2);
graph.insertEdge(two, three, 8);
graph.insertEdge(one, three, 5);
graph.insertEdge(three, four, 10);
graph.insertEdge(three, five, 15);
graph.insertEdge(four, six, 2);
graph.insertEdge(five, six, 6);

var dijkstra = GraphAlgorithms.shortestPathLengths(graph, zero);
for (var vertex : dijkstra.entrySet()) {
    System.out.println("Start Vertex: " + zero.getElement() + " -> " +
            vertex.getKey().getElement()
            + ", Distance: " + vertex.getValue());
}

Minimum Spanning Tree `MST`

Imagine you've got a bunch of scattered islands (vertices) and a limited budget for bridges (edges with weights). An MST is that clever little subset of bridges that connects every single island, using the absolute minimum amount of bridge-building material possible, all while avoiding any silly circular detours (cycles). Essentially, it's the "cheapest" and most efficient way to wire up your entire network without creating any redundant loops.

When tackling this problem, you'll meet two algorithms: Kruskal's Algorithm and Prim's Algorithm. They're both inherently greedy, always making the seemingly selfish choice at each step to get the job done.

Kruskal's algorithm

Kruskal's Algorithm, works by iteratively snatching up the lowest-weight edge it can find, as long as it doesn't create a cycle in our growing Minimum Spanning Tree. It keeps doing this until every single vertex has been personally invited to the party.

In essence, Kruskal's is the super-organized type: it first lines up all the graph's edges from smallest to largest, like a meticulous librarian. Then, it goes down the line, adding edges and nodes to the MST only if they promise not to cause a cyclical drama. It's all about picking the feather-light edges first and saving the heavy lifters for last. And for the grand finale? It gracefully merges any trees that haven't quite connected yet, like a matchmaker bringing lonely branches together.

Now, as for implementing this genius... ah, my dear friends, I shall leave that thrilling adventure to your capable hands.

Prim's Algorithm

Meet Prim's Algorithm, the other star in our MST show! If Kruskal's is the meticulous librarian, Prim's is more of a social climber. It's another greedy guru for finding the minimum spanning tree of a weighted, undirected graph.

How does it work? Imagine Prim's starting from an arbitrary vertex (like picking a random person at a party). Then, it continuously sniffs out the absolute cheapest connection that links its ever-expanding social circle (the growing tree) to someone new (a fresh vertex). It keeps adding these 'best new friends' until everyone at the party is connected in the most cost-effective way possible! No cycles allowed, just efficient networking.

For our implementation, we're getting super organized! We'll be using an ArrayList<Edge<V>> to neatly store all the edges that make it into our MST. To steer clear of the dreaded cycle, we've got a trusty HashSet on standby, ready to mark vertices as 'visited.'

And, of course, no heroic journey is complete without our hero: the PriorityQueue. Our algorithm will embark on an iterative quest, starting from the source, meticulously adding unvisited vertices to the queue and carefully selecting the edges to populate our ArrayList<Edge<V>>. It's all about precision, avoiding loops, and letting our PriorityQueue do the heavy lifting!

public static <V> ArrayList<Edge<V>> MST(Graph<V> graph, Vertex<V> source) {
      ArrayList<Edge<V>> tree = new ArrayList<>();
      HashSet<Vertex<V>> visited = new HashSet<>();

      Queue<Edge<V>> queue = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));
      queue.add(new Edge<>(source, null, 0));

      while (!queue.isEmpty()) {
          Edge<V> currentEdge = queue.poll();
          Vertex<V> currentVertex;

          if (currentEdge.getDestination() == null) {
              currentVertex = currentEdge.getOrigin();
          } else {
              currentVertex = currentEdge.getDestination();
          }

          if (!visited.contains(currentEdge.getOrigin()) || !visited.contains(currentVertex)) {
              Vertex<V> destination = currentEdge.getDestination();

              Edge<V> edge = destination == null ? null : graph.getEdge(currentEdge.getOrigin(), destination);
              if (edge != null) {
                  tree.add(edge);
              }
              visited.add(currentVertex);
              visited.add(currentEdge.getOrigin());
          }

          for (Edge<V> edge : graph.outgoingEdges(currentVertex)) {
              Vertex<V> vertex = edge.opposite(currentVertex);
              int weight = edge.getWeight();

              if (!visited.contains(vertex) || !visited.contains(currentVertex)) {
                  Edge<V> edgeWeight = new Edge<>(currentVertex, vertex, weight);
                  queue.offer(edgeWeight);
              }
          }
      }

      return tree;
  }

To prove Prim's algorithm, we're going to construct a graph in code that's identical to the figure below. This is where we see if all our hard work pays off. Dive into your main() method and add the code below.

AdjacencyMapGraph<Integer> graph = new AdjacencyMapGraph<>(false);

Vertex<Integer> one = graph.insertVertex(1);
Vertex<Integer> two = graph.insertVertex(2);
Vertex<Integer> three = graph.insertVertex(3);
Vertex<Integer> four = graph.insertVertex(4);
Vertex<Integer> five = graph.insertVertex(5);

// Insert edges 
graph.insertEdge(one, two, 2);
graph.insertEdge(one, three, 3);
graph.insertEdge(two, three, 1);
graph.insertEdge(two, four, 3);
graph.insertEdge(two, five, 2);
graph.insertEdge(four, five, 5);
graph.insertEdge(three, five, 1);

var mst = GraphAlgorithms.MST(graph, zero);
for (Edge<Integer> edge : mst) {
    System.out.println("Edge: " + edge.getOrigin().getElement() + " -> " +
            edge.getDestination().getElement() + ", Weight: " + edge.getWeight());
}

Graph In Java ☕

Knitely — Sat, 28 Jun 2025 18:22:34 +0000

Introduction

Get ready, because we're about to dive headfirst into the wild and wacky world of Graphs! Forget your boring old spreadsheets; here, we'll untangle their mysterious properties, get cozy with their vertices (the VIPs of the graph), navigate their edges (the scenic routes), master the art of traversal, and even learn how to draw them in a way that doesn't look like your cat walked across the keyboard (their representation). I'm hoping this post is more valuable than finding a twenty in your old jeans, but if you have any brilliant ideas, don't be shy – drop a comment below!

Graph

Picture a bunch of islands floating in the sea. Each island is a vertex. Now, imagine some beavers build bridges between certain islands. Those bridges? They're the edges. A graph is just the whole map showing where all the islands are and which ones are connected by a convenient bridge. It's a network of "who's connected to whom".

Viewed abstractly, a graph G is simply a set V of vertices and a collection E of pairs of vertices from V, called edges.

Basic terms of a graph

Directed edges in graphs are like one-way streets. If you have an edge (u, v) that's directed from u to v, it means you can travel from u to v, but you cannot go from v back to u using that same edge. The arrow (from the above figure) tells you which way the traffic flows. Now, for undirected edges, it's more like a two-way street or a friendly handshake. If there's an undirected edge between u and v, it means the connection goes both ways. You can absolutely travel from u to v, and just as easily from v to u. The lack of an arrow (from the above figure) implies this mutual connection.
The two vertices joined by an edge are called the end vertices (or endpoints) of the edge. For the undirected graph in the above figure, Vertex A and B are the endpoints for edge 2. If an edge is directed, its first endpoint is its origin (e.g., A) and the other is its destination (e.g., B), as seen with edge 3 in the above figure.
Two vertices u and v are said to be adjacent if there is an edge whose end vertices are u and v. In the above figure, A and B are adjacent because there is an edge between them for example, edge 2 in the undirected graph, or edge 3 even if directed from A to B.
An edge is said to be incident to a vertex if the vertex is one of the edge’s endpoints. In the above figure, edge 3 is incident to vertex B, and edge 4 is also incident to vertex B assuming vertex B is an endpoint of both edge 3 and edge 4. A vertex is incident with an edge if the vertex is one of the endpoints of that edge.
The outgoing edges of a vertex are the directed edges whose origin is that vertex. The incoming edges of a vertex are the directed edges whose destination is that vertex. In the above figure the vertex B has two outgoing edges (2 and 4) and one incoming edge (3) in the directed graph.
The degree of a vertex v is the number of incident edges of v. The in-degree and out-degree of a vertex v are the number of the incoming and outgoing edges of v, respectively.

We've navigated the dictionary of graph terms, and now it's time to get our hands dirty with some actual code to bring these concepts to life.

So, go ahead and fire up your favorite text editor and let's start sketching out the blueprint for our Graph.

The Vertex ADT

Before our graph can establish any type of connections, we must first define its fundamental building block: the vertex. Please create a Vertex.java file and add the following code.

public interface Vertex<V> {
    V getElement();

    void setIsVisited(boolean isVisited);

    boolean getIsVisited();

}

From the above code getElement() which is obvious return the element stored at the vertex, the other like getIsVisited() and setIsVisited() are used for indicating if the vertex is visited or not we will be using them in graph graph traversal section.

The Graph ADT

We've given our humble vertices a soul. Now, for the grand reveal: it's time to give the entire Graph some personality and give it the essential tricks 'expected functions' – we're training our magnificent Graph to perform.

numVertices(): Returns the number of vertices of the graph.

vertices(): Returns an iteration of all the vertices of the graph.

numEdges(): Returns the number of edges of the graph

insertVertex(x): Creates and returns a new Vertex storing element x.

insertEdge(u, v): Creates and an Edge from vertex u to vertex v, an error occurs if there already exists an edge from u to v.

outgoingVertices(v): returns the outgoing vertex connected to v.

incomingVertices(v): returns the incoming vertex connected to v.

outDegree(v): Returns the number of outgoing edges from vertex v.

inDegree(v): Returns the number of incoming edges to vertex v. For an undirected graph, this returns the same value as does outDegree(v).

Alright, It's time to get our abstract Graph concept into the harsh reality of Java ☕ code. We're not just defining it anymore; we're giving it a proper blueprint (a.k.a., an interface). So, buckle up, create that Graph.java file, and let's give it a life into with the code below.

public interface Graph<V> {
    int numVertices();

    int numEdges();

    Iterable<Vertex<V>> vertices();

    Vertex<V> insertVertex(V element);

    void insertEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException;

    V removeVertex(Vertex<V> v) throws IllegalArgumentException;

    Iterable<Vertex<V>> outgoingVertices(Vertex<V> v) throws IllegalArgumentException;

    Iterable<Vertex<V>> incomingVertices(Vertex<V> v) throws IllegalArgumentException;

    int outDegree(Vertex<V> v) throws IllegalArgumentException;

    int inDegree(Vertex<V> v) throws IllegalArgumentException;

}

Graph representation

Think of graph representation as the art of organizing a very, very busy brain. How do we store all those relationships – who knows whom, what leads where – inside a computer's limited gray matter so it can actually find things later without a complete meltdown? It's all about picking the right mental filing system.

We have to forget the other graph representations for now – we're going with the Adjacency List for totally obvious reasons.

We use an array as our main directory, where each spot is reserved for a vertex. But here's the clever bit: each array spot doesn't just hold the vertex; it points to a list of all that vertex's immediate pals or 'neighbors.' We call this its adjacency list.

So, if A is our array, A[i] leads you to 'Node i's' list. If 'Node i' is socially awkward and has no connections? A[i] will just point to null. look at the figure below for more understanding.

Adjacency List Implementation

We've done the theoretical hand-waving, now... it's time to get down to the nuts and bolts, the secret sauce, the absolute juicy core of our graph adventure: implementing the adjacency list with true grace.

This is where the real magic happens. So, create a new file called AdjacencyMapGraph.java, and let's start weaving some code spells.

Our master plan for this elegant implementation involves:

Using an ArrayList<Vertex<V>> to keep our vertices neatly organized (like a very tidy collection of digital action figures).
And, of course, the ever-important isDirected boolean will be our guiding star, letting us know if we're dealing with one-way streets (directed graph) or a free-for-all (undirected graph) network.

Let's make some magic happen in AdjacencyMapGraph.java with the code below.

import java.util.ArrayList;
import java.util.HashSet;

import dsa.graph.Graph;
import dsa.graph.Vertex;

public class AdjacencyMapGraph<V> implements Graph<V> {
    private boolean isDirected;
    private int numEdges;
    private ArrayList<Vertex<V>> vertices = new ArrayList<>();

    public AdjacencyMapGraph(boolean isDirected) {
        this.isDirected = isDirected;
    }
}

Now we need to dive into the nitty-gritty of what makes each individual vertex. Think of it like giving each of our graph citizens their own little private diary and address book.

So, let's conjure up a special internal class, which we'll call InnerVertex. This little powerhouse will quietly implement our Vertex interface.

Inside this InnerVertex's digital brain, we're going to give it two super-speedy rolodexes: outgoing and incoming. These will be HashSet<Vertex<V>> because, let's be honest, we're obsessed with that glorious O(1) time complexity. outgoing and incoming variables will be the same if the graph is undirected. This way, our InnerVertex can instantly know who it's sending signals to and who's sending signals its way.

And just to keep things super organized, each InnerVertex will also remember its own 'seat number' – an index member that tells us exactly where it's chilling in our main vertices array.

Alright, enough with the briefing! It's time to get down to business. Head back to your AdjacencyMapGraph.java file and let's embed this clever little helper with the code below. Get ready to sprinkle some more magic!

 public AdjacencyMapGraph(boolean isDirected) {
    this.isDirected = isDirected;
}

protected static class InnerVertex<V> implements Vertex<V> {
    private V element;
    private int index;
    private boolean isVisited;
    private HashSet<Vertex<V>> outgoing, incoming;

    public InnerVertex(V element, boolean isDirected) {
        this.element = element;
        outgoing = new HashSet<>();
        if (isDirected) {
            incoming = new HashSet<>();
        } else {
            incoming = outgoing;
        }

    }

    @Override
    public void setIsVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }

    @Override
    public boolean getIsVisited() {
        return isVisited;
    }

    public V getElement() {
        return element;
    }

    public HashSet<Vertex<V>> getOutgoing() throws IllegalArgumentException {
        return outgoing;
    }

    public HashSet<Vertex<V>> getIncoming() throws IllegalArgumentException {
        return incoming;
    }

    public int getIndex() {
        return this.index;
    }

    public void setIndex(int index) {
        this.index = index;
    }
}

Alright, we've designed our fancy InnerVertex with all its clever internal workings. Now, it's time to equip our AdjacencyMapGraph with its fundamental housekeeping rules and, most importantly, a very strict validator validate(Vertex<V> v), Think of it as our graph's quality control department, making sure only our kind of vertices (the InnerVertex kind) are allowed to play in our exclusive graph club.

    public void setIndex(int index) {
        this.index = index;
    }
}

private InnerVertex<V> validate(Vertex<V> v) {
    if (!(v instanceof InnerVertex))
        throw new IllegalArgumentException("Invalid vertex");
    InnerVertex<V> vertex = (InnerVertex<V>) v;
    return vertex;
}

@Override
public int numVertices() {
    return vertices.size();
}

@Override
public int numEdges() {
    return numEdges;
}

@Override
public Iterable<Vertex<V>> vertices() {
    return vertices;
}

@Override
public Vertex<V> insertVertex(V element) {
    InnerVertex<V> vertex = new InnerVertex<>(element, isDirected);
    vertices.add(vertex);
    vertex.setIndex(vertices.size() - 1);
    return vertex;
}

@Override
public int outDegree(Vertex<V> v) throws IllegalArgumentException {
    InnerVertex<V> origin = validate(v);
    return origin.getOutgoing().size();
}

@Override
public int inDegree(Vertex<V> v) throws IllegalArgumentException {
    InnerVertex<V> destination = validate(v);
    return destination.getIncoming().size();
}

@Override
public Iterable<Vertex<V>> outgoingVertices(Vertex<V> v) throws IllegalArgumentException {
    InnerVertex<V> outgoing = validate(v);
    return outgoing.getOutgoing();
}

@Override
public Iterable<Vertex<V>> incomingVertices(Vertex<V> v) throws IllegalArgumentException {
    InnerVertex<V> incoming = validate(v);
    return incoming.getIncoming();
}

Alright, next we've to add our meticulous validators and our keen-eyed "are-they-even-here-or-already-friends?" checkers (our isValidVertex and hasEdge methods). Head back to AdjacencyMapGraph.java add the code below.

    public void setIndex(int index) {
        this.index = index;
    }
}

 private boolean hasEdge(Vertex<V> u, Vertex<V> v) {
    InnerVertex<V> origin = validate(u);
    InnerVertex<V> destination = validate(v);
    return origin.getOutgoing().contains(destination);
}

private boolean isValidVertex(Vertex<V> v) {
    if (v == null) {
        return false;
    }

    InnerVertex<V> vertex = validate(v);
    int index = vertex.getIndex();
    if (index < vertices.size() && vertices.get(index) == vertex) {
        return true;
    }
    return false;
}

Now that all the pre-flight checks are in place, we can finally and happily, write the big one: our insertEdge(Vertex<V> u, Vertex<V> v) method. Let's give our AdjacencyMapGraph.java the power to make relationships! Go ahead and add the following code.

        InnerVertex<V> vertex = validate(v);
    int index = vertex.getIndex();
    if (index < vertices.size() && vertices.get(index) == vertex) {
        return true;
    }
    return false;
}

@Override
public void insertEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException {
    if (!isValidVertex(u) || !isValidVertex(v)) {
        throw new IllegalArgumentException("Invalid vertex");
    }

    if (!hasEdge(u, v)) {
        InnerVertex<V> origin = validate(u);
        InnerVertex<V> destination = validate(v);
        origin.getOutgoing().add(destination);
        destination.getIncoming().add(origin);
        numEdges++;
    } else
        throw new IllegalArgumentException("Edge from u to v exists");
}

Alright, we've brought vertices into existence, we've played matchmaker with edges, and now... it's time for the less glamorous but equally essential task: ejecting a vertex.

Sometimes, a vertex just needs to go. But before we send it packing, we have to be polite and disconnect all its social ties first using our removeEdge() method. Can't have any dangling digital friendships, after all.

And here's where we get really clever to avoid a massive performance headache. Normally, if you yank a vertex out of the middle of an array, everything after it has to awkwardly shuffle forward, which is a slow O(N) dance. But we're too smart for that.

Instead, we're going to pull a fast one: when we remove a vertex, we'll grab the very last vertex in our vertices array and plop it right into the empty spot using the index inside the vertex. Then, we simply snip off the now-redundant last element. It's like a quick game of musical chairs to fill the gap instantly, making our removal almost ridiculously fast (a glorious O(1)). No tedious shifting required.

So, get ready to implement this elegantly brutal "eviction" strategy. Head back to AdjacencyMapGraph.java and let's add the code to gracefully removed vertex.

            destination.getIncoming().add(origin);
        numEdges++;
    } else
        throw new IllegalArgumentException("Edge from u to v exists");
}

private void removeEdge(HashSet<Vertex<V>> edges, Vertex<V> vertex, boolean isOutgoing) {
    for (Vertex<V> ve : edges) {
        InnerVertex<V> vert = validate(ve);
        if (isOutgoing) {
            vert.getIncoming().remove(vertex);
        } else {
            vert.getOutgoing().remove(vertex);
        }
        numEdges--;
    }
    edges.clear();
}

@Override
public V removeVertex(Vertex<V> v) throws IllegalArgumentException {
    V temp = v.getElement();
    InnerVertex<V> vertex = validate(v);

    HashSet<Vertex<V>> outgoing = vertex.getOutgoing();
    removeEdge(outgoing, vertex, true);

    HashSet<Vertex<V>> incoming = vertex.getIncoming();
    removeEdge(incoming, vertex, false);

    int index = vertex.getIndex();
    int size = vertices.size();
    if (index != size - 1) {
        InnerVertex<V> lastVertex = validate(vertices.get(size - 1));
        lastVertex.setIndex(index);
        vertices.set(index, lastVertex);
    }

    vertices.remove(size - 1);
    vertex = null;
    v = null;
    return temp;
}

Graph traversal algorithms

Alright, our dandy graph has been built, it's got its charming vertices, and it knows how to make (and break) connections. But what's a magnificent map if you can't actually explore it?

Now, it's time for our graph to embark on some grand adventures! We're talking about traversal algorithms, which are essentially fancy ways for our graph to go on a tour, visiting each of those cute little vertices and intriguing edges.

On this particular post, we're going back to basics, visiting the wise elders of the traversal world: the good old Depth-First Search (DFS) and Breadth-First Search (BFS). Think of them as two very different, but equally effective, tour guides for navigating the twists and turns of our graph. One's a deep diver, the other's a wide explorer.

Depth-First Search (DFS)

Depth-First Search (DFS) is basically that friend who, when faced with a multi-story building, immediately bursts into the first room they see and then just keeps going. "Oh, a door! What's behind that door? Another door! Let's see where that one leads!"

It's like DFS gets tunnel vision. It'll plunge down into the deepest, darkest corner of the basement, exploring every nook and cranny of that one path before it even considers glancing at another room on the first floor. It carries a trusty stack to remember where it was before it got distracted by the shiny new path, like a pile of "oops, gotta backtrack eventually" notes. It's not about levels, it's about seeing how deep the rabbit hole goes.

Alright, we've got the lowdown on what DFS is all about! Now it's time to roll up our sleeves and get our hands dirty by implementing it on our trusty, dandy Graph. We're gonna let it explore all its precious vertices. So go on, create GraphAlgorithms.java file and write the following code right inside.

public class GraphAlgorithms {

    public static <V> void depthFirstSearch(Graph<V> graph, Vertex<V> start, ArrayList<Vertex<V>> visited) {
        start.setIsVisited(true);
        visited.add(start);
        for (Vertex<V> vertex : graph.outgoingVertices(start)) {
            if (!vertex.getIsVisited()) {
                depthFirstSearch(graph, vertex, visited);
            }
        }
    }

    public static <V> ArrayList<Vertex<V>> depthFirstSearchComplete(Graph<V> graph) {
        ArrayList<Vertex<V>> snapshot = new ArrayList<>();
        for (Vertex<V> vertex : graph.vertices()) {
            if (!vertex.getIsVisited()) {
                depthFirstSearch(graph, vertex, snapshot);
            }
        }
        return snapshot;
    }

}

Our depthFirstSearch() method starts exploring your graph from a chosen vertex, then recursively visits all connected vertices it hasn't seen yet. To make sure every single vertex in the graph gets explored, even if it's disconnected, our depthFirstSearchComplete() method loops through all vertices and calls depthFirstSearch() for any that haven't been visited yet.

Breadth-First Search (BFS)

Unlike its chaotic cousin (DFS), Breadth-First Search is the sensible, highly organized explorer. When faced with a multi-story building, it doesn't just plunge into the basement. Oh no! It meticulously clears out every room on the first floor, then every room on the second, and so on. It's all about exploring "level by level," methodically making its way through the structure. It carries a trusty queue to remember which rooms it still needs to check on the current floor.

Alright, We've got a good understanding of what BFS is all about. It's time to get our hands dirty by implementing it on our Graph. We're gonna let it explore all its precious vertices. So go on and add the following code inside GraphAlgorithms class.

      for (Vertex<V> vertex : graph.vertices()) {
        if (!vertex.getIsVisited()) {
            depthFirstSearch(graph, vertex, snapshot);
        }
    }
    return snapshot;
}

public static <V> void breadthFirstSearch(Graph<V> graph, Vertex<V> start, ArrayList<Vertex<V>> visited) {
    Queue<Vertex<V>> queue = new LinkedList<>();
    queue.add(start);
    start.setIsVisited(true);
    visited.add(start);

    while (!queue.isEmpty()) {
        Vertex<V> current = queue.remove();
        if (!current.getIsVisited()) {
            current.setIsVisited(true);
            visited.add(current);
        }

        for (Vertex<V> vertex : graph.outgoingVertices(current)) {
            if (!vertex.getIsVisited()) {
                queue.add(vertex);
            }
        }
    }
}

public static <V> ArrayList<Vertex<V>> breadthFirstSearchComplete(Graph<V> graph) {

    ArrayList<Vertex<V>> snapshot = new ArrayList<>();
    for (Vertex<V> vertex : graph.vertices()) {
        if (!vertex.getIsVisited()) {
            breadthFirstSearch(graph, vertex, snapshot);
        }
    }

    return snapshot;
}

public static <V> void resetVisitedVertices(ArrayList<Vertex<V>> visited) {
    for (Vertex<V> vertex : visited) {
        vertex.setIsVisited(false);
    }
}

resetVisitedVertice() method is used for un-visiting the visited vertices.

Alright, it seems our initial dive into the world of Graphs has reached its surface. While we've only skimmed the top of this fascinating subject, covering the essential basics like vertices, edges, traversal, and representation, there's a whole ocean of advanced topics awaiting us.

We deliberately kept this post concise to ensure you grasped the fundamental concepts without getting lost. In upcoming posts, we'll dive and explore much deeper.

Now that we've finished writing the post, we need to test what we've written so far. So, go to your main() method and add the following code.

 public static void main(String[] args) throws Exception {
        AdjacencyMapGraph<Integer> graph = new AdjacencyMapGraph<>(true);

        Vertex<Integer> one = graph.insertVertex(1);
        Vertex<Integer> five = graph.insertVertex(5);
        Vertex<Integer> three = graph.insertVertex(3);
        Vertex<Integer> four = graph.insertVertex(4);
        Vertex<Integer> two = graph.insertVertex(2);
        Vertex<Integer> seven = graph.insertVertex(7);
        Vertex<Integer> eight = graph.insertVertex(8);

        // Insering an edge
        graph.insertEdge(one, three);
        graph.insertEdge(one, five);
        graph.insertEdge(five, four);
        graph.insertEdge(five, two);

        graph.insertEdge(three, eight);
        graph.insertEdge(three, seven);

        var visited = GraphAlgorithms.depthFirstSearchComplete(graph); // [1, 5, 2, 4, 3, 8, 7]
        for (Vertex<Integer> vertex : visited) {
            System.out.print(vertex.getElement() + ", ");
        }

        GraphAlgorithms.resetVisitedVertices(visited);
        System.out.println("\n-- BFS Visited ---");

        var bfsVisited = GraphAlgorithms.breadthFirstSearchComplete(graph); // [1, 5, 3, 2, 4, 8, 7]
        for (Vertex<Integer> vertex : bfsVisited) {
            System.out.print(vertex.getElement() + ", ");
        }
}

The graph we create on the code is the same as the graph in the figure below.

HashMap in Java

Knitely — Sun, 22 Jun 2025 18:43:06 +0000

Introduction

Ever wonder how your computer keeps track of everything without losing its mind? Well, a big round of applause goes to Maps! In this post, we're going to peek behind the curtain and discover what makes them tick, why they're so incredibly handy, and how they manage to stay so organized, even when things get a little chaotic. We've distilled the wisdom of "Data Structures and Algorithms in Java™" down to its most digestible (and least clunky) form, just for you. So, read on, enjoy, and then tell us what you think – we're all ears!

Map

Let's talk about Maps, the ultimate VIP section for your data!
Imagine you have a super-exclusive club, and every guest (that's your value) needs a special, one-of-a-kind invitation (that's your key) to get in. You can't just waltz in; you need the key.

A Map is basically that club's bouncer and coat check, rolled into one super-efficient, digital package. It's an Abstract Data Type (ADT) designed to:

Efficiently store: Think of it as a meticulously organized closet where everything has its designated spot.
Retrieve values: Want your coat back? Just show your coat-check ticket (the key), and poof! Your coat (the value) is in your hands.
Based upon a uniquely identifying search key for each: This is the crucial part. Each key is like a fingerprint – no two are alike! If two keys were the same, how would the bouncer know which "value" to give you?

So, in essence, a Map just stores key-value pairs (k, v), which we lovingly call entries. 'k' is your secret handshake, your golden ticket, your "open sesame." And 'v' is the treasure that opens up.

It's like a super-smart dictionary, but instead of words and definitions, it's whatever awesome stuff you want to link together! Need to find your friend Bob's phone number? Just look up "Bob" (the key) and BAM! There's his number (the value).

The Map Interface

Let us define our interface for our map, fire up your favorite text editor, and let's craft the blueprint for our magnificent, dandy map. It's time to give it a personality and some rules.

Go ahead and create a file named Map.java, and then, write in the code I just gave you.

import java.util.Map.Entry;

public interface Map<K, V> {
    int size();

    boolean isEmpty();

    V get(K key);

    V put(K key, V value);

    V remove(K key);

    Iterable<K> keySet();

    Iterable<V> values();

    Iterable<Entry<K, V>> entrySet();
}

The `AbstractMap.java` class

Now our map M as been given a personality. We've established the ground rules for its existence. Then we have to give our attention to an important thing the sacred vows M must uphold, the operations it is obligated to perform.
Behold, the glorious operations where M gracefully execute:

keySet(): Returns an iterable collection containing all the keys stored in M.

values(): Returns an iterable collection containing all the values of entries stored in M (with repetition if multiple keys map to the same value).

size(): Returns the number of entries in M.

isEmpty(): Returns a boolean indicating whether M is empty

To make our map M real and useful, we must implement these operations, So go ahead and create AbstractMap.java file, An abstract class that implements the grumpy Map interface, but instead of doing all the work by itself, it strategically leaves some methods (shoving the responsibility onto its subclasses) while cunningly implementing others by relying on those methods.

Before we start our implementation I have to warn you of some things, keySet() and values() heavily depend on Iterator and Iterable interfaces which will not be discussed on this post for obvious reasons. So go ahead and do your research about them. And we will use Java’s Entry interface from java.util.Map.Entry for our MapEntery class.

Think of MapEntery as Node in linked list it is a simple class that holds the key and value (entry) of a map.

Go to AbstractMap.java and add the following code in it.

import java.util.Iterator;
import java.util.Map.Entry;

public abstract class AbstractMap<K, V> implements Map<K, V> {
    protected int size = 0;

    protected static class MapEntry<K, V> implements Entry<K, V> {
        private K key;
        private V value;

        public MapEntry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
    }

    // Implementation of Iterable for keys
    private class KeyIterate implements Iterator<K> {
        private Iterator<Entry<K, V>> entries = entrySet().iterator();

        @Override
        public boolean hasNext() {
            return entries.hasNext();
        }

        @Override
        public K next() {
            return entries.next().getKey();
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    private class KeyIterable implements Iterable<K> {
        @Override
        public Iterator<K> iterator() {
            return new KeyIterate();
        }
    }

    @Override
    public Iterable<K> keySet() {
        return new KeyIterable();
    }

    // Implementation of Iterable for values
    private class ValueIterate implements Iterator<V> {
        private Iterator<Entry<K, V>> entries = entrySet().iterator();

        @Override
        public boolean hasNext() {
            return entries.hasNext();
        }

        @Override
        public V next() {
            return entries.next().getValue();
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    private class ValueIterable implements Iterable<V> {
        @Override
        public Iterator<V> iterator() {
            return new ValueIterate();
        }
    }

    @Override
    public Iterable<V> values() {
        return new ValueIterable();
    };

    // Implementation of size and isEmpty methods
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

}

The Hash Tables

Now let's talk about the Hash Table (also known as a Hash Map) – the superhero of Maps, but with a wonderfully weird superpower!

So, a Hash Table is basically a map M, but instead of just neatly filing things alphabetically or in some predictable order, it hires this Hash Function to:

Take your "key"
And, with a dramatic POOF and maybe a little wiggle, transform it into a corresponding indices in a table from 0 to N - 1, where N is length of the table look at the figure bellow a table length of 11. containing entries (1, D), (3, Z), (6, C), and (7, Q).

As a result, we will conceptualize our table as a bucket array, In which each bucket may manage a collection of entries that are sent to a specific index by the hash function.

Hash Function

The Hash Function (let's call it 'h'), The ultimate mission for h is simple yet crucial:

h's Job: To take any crazy, unique key k you throw at it h(k) and spit out a perfectly non-random-at-all-but-appears-random whole number.

This number must be between 0 and N-1. Think of N as the total number of perfectly sized, pre-labeled storage bins M has available. So, h's only goal is to turn your weird key into a valid bin number, ensuring your data has a designated, immediately accessible spot in one of M's N buckets.

If there are two or more keys with the same hash value, then two different entries will be mapped to the same bucket in M. In this case, we say that a the dreaded collision has occurred. A hash function is labeled “good” if it maps the keys in our map so as to sufficiently minimize the dreaded collisions.

Hash function, h(k) consisting of two portions a hash code that maps a key k to an integer, and a compression function that maps the hash code to an integer within a range of indices, [0, N −1].

Hash Codes

The first action that a hash function performs is to generate an integer i for a key k; this integer need not be in the range [0, N −1], and may even be negative shocking!! We desire that the set of hash codes assigned to our keys should avoid the dreaded collisions as much as possible.
These are the theories on how to build an efficient hash code (We are not going to use them in this post. Instead, we will use Java’s own hashCode() method to get our beloved hash codes).

Polynomial Hash Code.

Polynomial hash code uses multiplication by different powers as a way to spread out the influence of each component across the resulting hash code.

Basically, it uses multiplication and addition. For a given key k with a length of n, it follows this expression:

hash(k) = k[0] + k[1]×a *+ k[2]×a^2+⋯+k[*n − 1]×a ^(n − 1)

Here ‘a’, is non-zero integer that is different from 1, it is highly recommended for it to be any of this numbers 33, 37, 39 and 41.

Cyclic-Shift Hash Code.

Cyclic-Shift Hash Code is a type of hash code generation method that involves shifting the bytes of a key k in cyclic manner.

This process uses bitwise shifting, including both left and right cyclic rotations, where bits move from one end to the other. For example:

The cyclic rotation for binary number 1110 000 by 4-bit results in 0000 1110

An implementation of acyclic-shift hash code computation for a character string in Java appears as follows:

static int hashCode(String s) {
    int h = 0;
    for (int i = 0; i < s.length(); i++) {
        h = (h << 5) | (h >>> 27);
        h += (int) s.charAt(i);
    }
    return h;
}

Its is expected for equivalent keys to have the same hash code so that they are guaranteed to map to the same bucket.

Compression Function

So, our eccentric Hash Function h is a brilliant artist, spitting out "hash codes" – big, sometimes even negative, numbers.

The problem? Our Map M only has a limited number of neatly numbered buckets (from 0 to N-1). h's wild splatters are usually way outside that neat little range.

That's where the Compression Function steps in! It's like M's tidy-up crew. Their job is to take h's grand, but often unruly, number and expertly squish it, fold it, or just generally re-map it into one of those perfectly valid [0, N-1] bucket spots.

The Division Method

In division method we map key k hash code integer i into one of N slots by taking reminder of of N.

h(k) = i mode n

And here are the rules we have to follow for ‘good’ hash compression.

N should not be a power of 2, if N = 2^p, h(k) is just the lowest p order bits of k example.:

Let N = 16 = 2^4 (p = 4)

If k = 42 (0010 1010) 42 % 16 = 10 (1010), 1010 is the last 4-bit of (0010 1010)
The size of N should be a prime number not too close to an exact power of 2.

The MAD Method

The MAD Method is like a super-smart pattern-disruptor. It takes that incoming number i (the hash code integer) and gives it a sophisticated, mathematical shake-up to scramble any hidden patterns before assigning it a bucket, by turning into:

[ (a×i + b) mod p ] mod N

Where:

a and b are just some random, friendly numbers M picks to add a bit of chaos.
N is the total number of buckets.
p is a prime number larger than N.

So, the MAD method ensures those hash codes are really spread out, giving each key its own happy, less-collided-with spot in M's storage!

In this post we will use the MAD method as a compression function for our magnificent map.

Now lets implement the hash table with a hash code and hash compression function, well also implement basic hash map function like get , remove and put.

Alright, enough theory! M's ready to get its hands dirty. We're about to give our has map the key-smashing "hash code," the number-wrangling "compression function," and teaching it to perform its essential magic: get, put, and remove .

Go ahead and create a AbstractHashMap.java write the following code inside it.

import java.util.ArrayList;
import java.util.Random;
import java.util.Map.Entry;

import dsa.maps.AbstractMap;

public abstract class AbstractHashMap<K, V> extends AbstractMap<K, V> {

    protected int n = 0; // number of entries in the map
    protected int capacity; // size of the hash table
    private int prime; // prime factor for the hash function
    private long scale, shift; // scaling and shifting factor for the hash function

    public AbstractHashMap(int capacity, int prime) {
        this.capacity = capacity;
        this.prime = prime;
        Random rand = new Random();
        this.scale = rand.nextInt(prime - 1) + 1;
        this.shift = rand.nextInt(prime);
        createTable();
    }

    public AbstractHashMap(int capacity) {
        this(capacity, 109345121);
    }

    public AbstractHashMap() {
        this(17);
    }

    // Public methods
    @Override
    public int size() {
        return n;
    }

    @Override
    public V get(K key) {
        return bucketGet(hashValue(key), key);
    }

    @Override
    public V remove(K key) {
        return bucketRemove(hashValue(key), key);
    }

    @Override
    public V put(K key, V value) {
        V answer = bucketPut(hashValue(key), key, value);
        if (n > capacity / 2) { // load factor threshold make it bellow 0.5
            resize(2 * capacity - 1); // find the next prime number
        }

        return answer;
    }

    // Private utility method
    private int hashValue(K key) {
        int code = key.hashCode();
        return (int) ((Math.abs(code * scale + shift) % prime) % capacity);
    }

    private void resize(int newCapacity) {
        ArrayList<Entry<K, V>> buffer = new ArrayList<>(n);
        for (Entry<K, V> entry : entrySet()) {
            buffer.add(entry);
        }
        capacity = newCapacity;
        createTable();
        n = 0;
        for (Entry<K, V> entry : buffer) {
            put(entry.getKey(), entry.getValue());
        }

    }

    // Protected methods to be implemented by subclasses
    protected abstract void createTable();

    protected abstract V bucketGet(int h, K key);

    protected abstract V bucketPut(int h, K key, V value);

    protected abstract V bucketRemove(int h, K key);

}

Here, the hashValue(K key) method is a hash function. We have a resize(int newCapacity) method that resizes the table to the new capacity (a prime number). If you look closely, this method is called only when we pass a load factor threshold (we will discuss this in the next section).

We pass 17 a prime number as a capacity for the table.

Collision Handling

The Load Factor, it’s just M's way of checking how crowded its storage facility is! It's simply the number of items n M is currently holding divided by the total number of bins N M actually has.

Think of it as: "How full are M's shelves?" If it gets too high, M might start to feel a bit cramped and slow down, leading to more dreaded collisions! It is also used for indicating if a table needs to be resized.

Load factor (α) = n / N

So, we need to set a certain load factor threshold for our map to resize the hash table and rehash it, meaning reinserting all entries into the newly resized table. In our code above, we set our load factor threshold to 0.5 in order to avoid the dreaded collision again.

Separate Chaining

Instead of just one item per bucket, M says, "No problem! Each bucket A[j] will just get its own little sub-container – like a tiny, extra-organized backpack!"

So, if multiple keys hash to bucket j, they all happily chill together in that bucket's personal backpack. When M needs something from bucket j, it just checks that bucket's little sub-container. It's like having a shared locker, but everyone gets their own neatly organized drawer inside.

Now that we have gotten the theories of separate chaining out of the way, let's implement it! So, go create the ChainHashMap.java file and add the following code. Here, we will implement these methods AbstractHashMap delegated to it for implementation:

createTable(): This method should create an initially empty table having size equal to a designated capacity instance variable.

bucketGet(h, k): This method should mimic the semantics of the public get method, but for a key k that is known to hash to bucket h.

bucketPut(h, k, v): This method should mimic the semantics of the public put method, but for a key k that is known to hash to bucket h.

bucketRemove(h, k): This method should mimic the semantics of the public remove method, but for a key k known to hash to bucket h.

entrySet(): This standard map method iterates through all entries of the map.

We will implement these methods for ProbeHashMap class that will implement in the next section. Enough talk! go to ChainHashMap.java file and add this code.

package dsa.maps.hashMap;

import java.util.ArrayList;
import java.util.Map.Entry;

public class ChainHashMap<K, V> extends AbstractHashMap<K, V> {
    private ArrayList<MapEntry<K, V>>[] table;

    public ChainHashMap() {
        super();
    }

    public ChainHashMap(int capacity) {
        super(capacity);
    }

    public ChainHashMap(int capacity, int prime) {
        super(capacity, prime);
    }

    private int findIndex(K key, ArrayList<MapEntry<K, V>> bucket) {
        for (int i = 0; i < bucket.size(); i++) {
            if (key.equals(bucket.get(i).getKey())) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public Iterable<Entry<K, V>> entrySet() {
        ArrayList<Entry<K, V>> entries = new ArrayList<>();
        for (ArrayList<MapEntry<K, V>> bucket : table) {
            if (bucket != null) {
                for (MapEntry<K, V> entry : bucket) {
                    entries.add(entry);
                }
            }
        }
        return entries;
    }

    @Override
    protected void createTable() {
        table = (ArrayList<MapEntry<K, V>>[]) new ArrayList[capacity];
    }

    @Override
    protected V bucketGet(int h, K key) {
        ArrayList<MapEntry<K, V>> bucket = table[h];
        int index = findIndex(key, bucket);
        if (index == -1) {
            return null;
        }

        return bucket.get(index).getValue();
    }

    @Override
    protected V bucketPut(int h, K key, V value) {
        ArrayList<MapEntry<K, V>> bucket = table[h];
        if (bucket == null) {
            bucket = new ArrayList<MapEntry<K, V>>();
            table[h] = bucket;
        }

        MapEntry<K, V> entry = new MapEntry<K, V>(key, value);
        bucket.add(entry);
        n++;
        return value;
    }

    @Override
    protected V bucketRemove(int h, K key) {
        ArrayList<MapEntry<K, V>> bucket = table[h];
        int index = findIndex(key, bucket);
        if (index == -1) {
            return null;
        }

        V temp = bucket.get(index).getValue();
        int size = bucket.size();
        if (index != size - 1) {
            bucket.set(index, bucket.get(size));
        }
        bucket.remove(size - 1);
        return temp;
    }

}

Our implementation uses a table, which is an array of ArrayList containing MapEntry<K, V> objects. Additionally, we use the findIndex(key, bucket) helper method to locate and return the index of a matched key within a specific bucket found at a given index in the table.

When an entry is removed from map M via bucketRemove(int h, K key), we first obtain an ArrayList L at a specific index derived from key k. We then find the index of key k within list L. Subsequently, we set the last element from list L to the index where k resided and remove the entry from that last index.

Open Addressing

Okay, so if "Separate Chaining" was like giving each bucket its own little backpack, "Open Addressing" is totally different!

Imagine M (our Map) has a very strict policy, Where every single item must live directly inside one of M's main buckets.

If M goes to put something in a bucket and finds it's already occupied (the dreaded collision!), it doesn't just make a new list. Oh no. It grumpily starts searching for the next available empty slot right there in the main table.

And when you ask M to get something? It zips to the expected bucket. If it's not there, M then systematically checks other nearby slots until it finds your item or declares, "Nope, not here!".

Open addressing requires that the load factor is always at most 1. For this post, we're going to dive headfirst into the Linear Probing method. Why? Because it's straightforward, gets the job done, and frankly, the others (Double Hashing, Quadratic Probing – meh!) are just too much effort for this discussion. Obvious reasons, you know. We like simplicity here!

Linear Probing

Imagine M tries to put a new item (k, v) into its assigned bucket A[j]. But oops! Someone's already sitting there.

Instead of panicking, M just says, "Excuse me, is A[(j+1) mod N] open?" (That's the very next bucket in line, wrapping around to the beginning if it hits the end).

If that one's also taken, M just keeps politely shuffling, one step at a time: "How about A[(j+2) mod N]? ...No? Okay, A[(j+3) mod N]?" And so on, until it finds an empty seat.

It's like searching for a parking spot in a crowded lot: you go to your assigned row, and if it's full, you just slowly inch forward, checking the very next spot until you find an open one! Simple, effective, and gets the job done.

But we face a serious issue when we remove an element from the table, Imagine you remove the car from spot #5 that is 5 (look at the above figure). Now that spot is empty. Later, M goes looking for car 16 which is on the spot #7, so it start probing from spot #4, But when M gets to the now-empty spot #5, it thinks, "Oh, no car here, must mean 16 isn't in the lot!" and gives up.

The solution? A special little "Ghost Car" or "Defunct Sentinel".

When M removes a car, it doesn't leave the spot truly empty. It puts a little "Ghost Car" (or a "Defunct" sign) there instead.

For get: M will politely skip over these Ghost Cars, knowing they're just placeholders, and keep searching until it finds the real car or a truly empty spot.
For put: If M encounters a Ghost Car while looking for a spot, it remembers, "Aha! This is a perfectly good, reusable spot for a new car!" and might just park there.

So, the "Defunct Sentinel" is M's clever way of making sure it never gets confused by a prematurely empty parking spot, ensuring smooth sailing (and finding!) even after removals.
Since we've finished all the preliminary discussions about linear probing, it's time for us to roll up our sleeves and get to the juicy part: implementing it! Go ahead and create the ProbeHashMap.java file, then add the following code.

package dsa.maps.hashMap;

import java.util.ArrayList;
import java.util.Map.Entry;

public class ProbeHashMap<K, V> extends AbstractHashMap<K, V> {
    private MapEntry<K, V>[] table;
    private MapEntry<K, V> DELETED = new MapEntry<>(null, null); // Marker for deleted entries

    public ProbeHashMap() {
        super();
    }

    public ProbeHashMap(int capacity) {
        super(capacity);
    }

    public ProbeHashMap(int capacity, int prime) {
        super(capacity, prime);
    }

    private boolean isAvailable(int i) {
        return table[i] == null || table[i] == DELETED;
    }

    private int findSlot(int h, K key) {
        int i = h;
        int available = -1;

        do {
            if (isAvailable(i)) {
                if (available == -1) {
                    available = i;
                }
                if (table[i] == null)
                    break;
            } else if (table[i].getKey().equals(key)) {
                return i; // Found the key
            }
            i = (i + 1) % capacity; // Linear probing cyclically
        } while (i != h);
        return -(available + 1);
    }

    @Override
    protected void createTable() {
        table = (MapEntry<K, V>[]) new MapEntry[capacity];
    }

    @Override
    protected V bucketGet(int h, K key) {
        int slot = findSlot(h, key);
        if (slot < 0) {
            return null;
        }
        return table[slot].getValue();
    }

    @Override
    protected V bucketPut(int h, K key, V value) {
        int slot = findSlot(h, key);
        if (slot >= 0)
            return table[slot].setValue(value);

        table[-(slot + 1)] = new MapEntry<>(key, value);
        n++;
        return value;
    }

    @Override
    protected V bucketRemove(int h, K key) {
        int slot = findSlot(h, key);
        if (slot < 0) {
            return null; // Key not found
        }
        V oldValue = table[slot].getValue();
        table[slot] = DELETED; // Mark as deleted
        n--;
        return oldValue;
    }

    @Override
    public Iterable<Entry<K, V>> entrySet() {
        ArrayList<Entry<K, V>> entries = new ArrayList<>();
        for (int i = 0; i < capacity; i++) {
            if (!isAvailable(i)) {
                entries.add(table[i]);
            }
        }

        return entries;
    }
}

We use the findSlot(int h, K key) method to probe the hash table cyclically, starting at the given index h. It returns a positive value when it finds an entry that matches k; otherwise, it returns a negative value.

Alright, my magnificent map-mastering comrades! We've journeyed through the wild realms of abstract data types, wrestled with grumpy interfaces, tamed eccentric hash functions, and even introduced a few "ghost cars" along the way. Our grand adventure with Maps in Java now reaches its glorious end.

So, open your Main.java file. Below, you'll find the code to call our Linear Probing warrior (the ProbeHashMap) This is where we see if code actually, you know, works.

Fair warning: We're only testing the Linear Probing part here. As for the Separate Chaining masterpiece? That, my dear, is your glorious homework assignment. M expects you to prove its chaining prowess yourself. After all, a true map explorer tests all their treasures!

 public static void main(String[] args) throws Exception {
      ProbeHashMap<String, Integer> myMap = new ProbeHashMap<>();
      myMap.put("January", 1);
      myMap.put("February", 2);
      myMap.put("March", 3);
      myMap.put("April", 4);
      myMap.put("May", 5);
      myMap.put("June", 6);
      myMap.put("July", 7);
      myMap.put("August", 8);
      myMap.put("September", 9);
      myMap.put("October", 10);
      myMap.put("November", 11);
      myMap.put("December", 13);

      System.out.println("March: " + myMap.get("March")); // 3
      System.out.println("Cherry: " + myMap.get("Cherry")); // null
      myMap.put("December", 12);
      System.out.println("December: " + myMap.get("December")); // 12

      myMap.remove("February");
      System.out.println("February: " + myMap.get("February")); // null
}

Tree In Java ☕

Knitely — Sat, 14 Jun 2025 10:28:33 +0000

Introduction

Welcome, Fellow Code Explorers!

Ever feel like your data is a tangled mess, scattered like socks after laundry day? Well, fear not, because today we're diving headfirst into the wonderful world of trees! No, not the leafy kind that photosynthesize (though those are pretty cool too). We're talking about the data structure kind, which are far more organized and, dare I say, less prone to bird nests.

In this post, we're going to unravel the mysteries of trees, from their roots (pun intended!) to their branches. We'll start with a solid definition and get acquainted with some fancy tree-related lingo. Then, we'll explore how to navigate these digital forests with traversal algorithms – think of it as finding your way without a GPS, but for data. Finally, and this is where the real fun begins, we'll roll up our sleeves and get our hands dirty with the implementation of trees using Java. So, if you've ever wanted to build your own digital arboretum, you're in the right place!

Now, a little heads-up: to truly appreciate the exquisite beauty of our Java implementation, a basic understanding of Java's Object-Oriented Programming (OOP) concepts – like generic classes, interfaces, and abstract classes – will be super helpful. If that last sentence made your eyes glaze over, don't panic! Just drop a comment below, and I might just whip up a "Java OOP for Dummies (Who Want to Conquer Trees)" post.

While I recommend following along section by section for maximum enlightenment (and minimal head-scratching), if you're a busy bee with places to be and code to conquer, feel free to fast-forward straight to the Implementation section. Just promise me you'll come back for the foundational stuff later! And hey, a little pro tip from your friendly neighborhood coder: grab a notebook! Jotting things down can make a world of difference.

For this grand adventure, I've leaned heavily on the wisdom found in "Data Structures and Algorithms in Java™" (a classic!) and received some minor assists from our good friends at GeeksforGeeks.

Your feedback is like sunshine to a programmer's soul, so please, don't be a stranger! Share your thoughts in the comments or follow my Telegram Channel. Let's make this post even better, together!

Definition

💡 Abstract Data Type (ADT) a mathematical model of a data structure that defines a set of operations on the data without specifying how the data is actually stored or implemented. Essentially, it's a blueprint or specification for how a data structure should behave, focusing on the "what" rather than the "how".

Think of a tree in the world of data structures not as something you'd climb for a picnic, but rather as the ultimate organizational chart. It's an abstract data type that loves to store elements in a neat, hierarchical fashion. And just like any good family tree (or corporate ladder), every element has a proud parent called p, except for that one big shot at the very top – the root – who's clearly self-made. Below them, you'll find zero or more children, diligently (or perhaps lazily) waiting their turn.

Formally, we define a tree T as a set of nodes storing elements, where these nodes have a parent-child relationship that satisfies some rather specific (and orderly!) properties:

If T is feeling non-empty, it proudly features a special node, humorously dubbed the root of T. This root node, much like a self-made entrepreneur, has no parent to report to.
Every other node n of T has a unique parent node w. And to keep things nice and tidy, every node with parent w is, by definition, a child of w. (No identity crises in our data trees!)

External, internal node and many more

Two nodes that are children of the same parent are siblings. A node v is external or a.k.a leaves If v has no children. A node v is internal if it has one or more children.

Edge: An edge is a connection between two nodes in a tree. In a rooted tree, edges link parent nodes to child nodes, forming hierarchical relationships.
Path: A path is a sequence of edges connecting one node to another. The length of the path is measured by the number of edges it contains.

An ordered tree is a type of tree in which the children of each node follow a specific order. This means that the arrangement of child nodes matters, and changing their sequence would result in a different tree structure. E.g. In a binary search tree (BST) (there will be a dedicated post about search tree coming soon.), the left child contains values smaller than the parent, and the right child contains values larger.

Traversal

Preorder Traversal

When it comes to a preorder traversal of a tree T, think of it as the ultimate "boss first" policy. The root of T gets all the attention and is visited immediately, soaking in the glory. Only after the root has had its moment in the spotlight do we then (and only then!) recursively traverse the sub-trees rooted at its children. It's like the CEO getting their coffee before anyone else – efficiency, right? You can find its implementation in Java here.

💡This is the pseudocode representation of the algorithm.

 func preorder(p):
        print p + ' ';
        for each child c in children(p) do
            preorder(c);

Postorder Traversal

Now, if preorder is the "boss first" type, then postorder traversal is decidedly more... familial. In a postorder traversal, we recursively traverse all the subtrees rooted at the children of the root first. We let the little ones have their fun, run around, and get everything sorted. Only after every single child and grandchild (and great-grandchild!) has been visited do we finally get around to visiting the root. It's like serving dessert to the kids before the parents get their main course.

You can find its implementation in Java here.

💡 This is the algorithm pseudocode

 func postorder(p):
        for each child c in children(p) do
            postorder(c);
        print p + ' ';

Breadth-First Tree Traversal BFS

Now, if preorder is the CEO and postorder is the clean-up crew, then Breadth-First Traversal (Level Order Traversal) is the ultimate party host! This technique is all about being fair and organized. We traverse the tree level by level, making sure everyone at the current depth d gets visited completely before we even think about moving on to the next depth d+1. It's like mingling with all the guests in the living room before you even consider heading to the kitchen.

And here's the kicker: this isn't some fancy recursive dive into subtrees. Oh no, we're far too systematic for that! Instead, we grab a handy-dandy queue, which ensures a strict FIFO (First-In, First-Out) policy. So, the first node we encounter at a level is the first one we process, making sure no one at the current depth d feels left out. It's democracy, but for data!

You can find its implementation in Java here.

Output: [[5], [12, 13], [7, 14, 2], [17, 23, 27, 3, 8, 11]] or [5, 12, 13, 7, 14, 2, 17, 23, 27, 3, 8, 11]

Explanation:
Level 0: Start with the root → [5]
Level 1: Visit its children → [12, 13]
Level 2: Visit children of 12 and 13 → [7, 14, 2]
Level 3: Visit children of 7, 4 and 12 → [17, 23, 27, 3, 8, 11]

💡 You can change level to depth they can be interchangeable

💡 Pseudocode for Breath First Search or BFS

func breadthfirst():
        Initialize queue Q to contain root();
        while Q not empty do
            p = Q.dequeue();
            print p + ', '; 
            for each child c in children(p) do
                    Q.enqueue(c);

💡 The standard preorder, postorder, and breadth-first traversals that were introduced for general trees can be directly applied to binary trees.

Inorder Traversal of a Binary Tree

If preorder is the boss and postorder is the cleanup crew, then inorder traversal is the quintessential "middle child syndrome" algorithm – specifically for binary trees! Informally, you can imagine it as visiting the nodes of T "from left to right," much like reading a perfectly ordered book. For every node p, we first (and meticulously!) traverse all the children in its left subtree. Only after that entire left side has been thoroughly explored do we finally get around to visiting p itself (the parent, the star of the show!). And then, once p has had its moment, we gracefully move on to traverse all the children in its right subtree. It's all about Left, then Parent, then Right – a very polite and sequential visit, indeed.

You can find its implementation in Java here.

💡 This is the algorithm pseudocode

  func inorder(p):
         if p has a left child lc then:
                 inorder(lc)
         print p + ', ';
         if p has a right child rc then
                 inorder(rc)

Implementing Tree On Java ☕

💡 First let us talk ( write on this case ) about position basically it is an interface that has only one method called getElement() that will return an element that is stored in it. We will implement this interface on the node class.

Why "Position" is Better for Tree Nodes (and Its Catch)

Alright, imagine you're trying to find your favorite snack in a massive, chaotic pantry (that's your tree, by the way). How do you locate that elusive bag of chips?

You might think, "Aha! I'll just give everything an index, like putting numbers on shelves!" Sounds smart, right? Well, in the world of trees, using indexes for nodes is like trying to navigate a dance party with a map that keeps changing.

Here's why indexes in trees are about as reliable as my New Year's resolutions:

Indexes are unstable: Picture this: you finally find your chips at index 7. But then, someone adds a giant box of cereal at the beginning of the shelf. Suddenly, your chips are now at index 8! Or worse, someone eats your chips (rude!) and removes them. Now index 7 points to a jar of pickles, or nothing at all! In tree-speak, if you remove or move a node, all the other indexes can shift faster than a cat knocking things off a counter. Trying to find a node by its old index? Good luck – you'll likely end up staring at the wrong thing, or worse, an empty spot where your data used to be.
Indexes are slow to find: Even if your indexes weren't playing musical chairs, finding a specific index in a tree is like trying to find a needle in a haystack by checking every single piece of hay. In the worst case, to find a node at a specific index, you might have to check every single node in the tree. For a large tree, that's what we call O(n) time – basically, it gets agonizingly slow as your tree (or pantry) grows.

This is precisely why we ditch the unreliable index system and embrace the glorious Position! Think of a position as a node's personal, unchangeable GPS coordinate or a permanent, unique "address" that it was born with.

And why is this Position thing so much better?

Positions are stable: A node's position is like its DNA – it stays the same no matter how many new nodes join the party, how many get kicked out, or if anyone rearranges the furniture. It's that unique ID tag that always points to the exact same node, no questions asked. It's the steadfast friend who never moves!
Positions are fast to find: Because each node has its own unique, unwavering position, you can go directly to it. No sifting through other nodes, no guessing games. This is what we call O(1) time – meaning it's lightning-fast, taking a constant amount of time regardless of whether your tree has five nodes or five million. It's like having a teleportation device straight to your data!

Now, for the catch (because there's always a catch, isn't there?): While positions are fantastically stable and fast, you actually have to store that unique position for each node if you want to find it later. It's like needing to remember your best friend's specific home address and postcode if you ever want to surprise them with pizza. It's worth it for the reliability, but it does mean a tiny bit more effort on your part to keep track of those precious positions!

To implement position create a Position.java file and add this code inside it.

public interface Position {
    E getElement() throws IllegalStateException;
}

Abstract Tree

The Tree Abstract Data Type

💡 We define a tree ADT using the concept of a position as an abstraction for a node of a tree. An element is stored at each position, and positions satisfy parent-child relationships that define the tree structure. for now consider position as a Node .

The position object for a tree support the method

getElement(): Returns the element stored at this position.
Accessor Methods

root(): Returns the position of the root of the tree (or null if empty).

parent(p): Returns the position of the parent of position p (or null if p is the root).

children(p): Returns an iterable collection containing the children of position p (if any).

numChildren(p): Returns the number of children of position p.
Query Method

isInternal(p): Returns true if position p has at least one child.

isExternal(p): Returns true if position p does not have any children.

isRoot(p): Returns true if position p is the root of the tree.
Other General Tree Methods

size(): Returns the number of positions (and hence elements) that are contained in the tree.

isEmpty(): Returns true if the tree does not contain any positions (and thus no elements).

iterator(): Returns an iterator for all elements in the tree (so that the tree itself is Iterable).

positions(): Returns an iterable collection of all positions of the tree.

💡 If an invalid position is sent as a parameter to any method of a tree, then an IllegalArgumentException is thrown.

We'll start by defining the Tree interface to list the basic functions required for any tree. Create the Tree.java file and add this code:

import java.util.Iterator;

public interface Tree<E> extends Iterable<E> {
    Position<E> root();

    Position<E> parent(Position<E> p) throws IllegalArgumentException;

    Iterable<Position<E>> children(Position<E> p) throws IllegalArgumentException;

    int numChildren(Position<E> p) throws IllegalArgumentException;

    boolean isInternal(Position<E> p) throws IllegalArgumentException;

    boolean isExternal(Position<E> p) throws IllegalArgumentException;

    boolean isRoot(Position<E> p) throws IllegalArgumentException;

    int size();

    boolean isEmpty();

    Iterator<E> iterator();

    Iterable<Position<E>> positions();

}

Next, we need an abstract class that will serve as a base for all tree types inheriting from it. Create an AbstractTree.java file and add this code to it.

public abstract class AbstractTree<E> implements Tree<E> { 
    // do something 
}

Next, we will add methods for querying the tree write this code on AbstractTree.java .

@Override
public boolean isEmpty() {
    return size() == 0;
}

@Override
public boolean isExternal(Position<E> p) throws IllegalArgumentException {
    return numChildren(p) == 0;
}

@Override
public boolean isInternal(Position<E> p) throws IllegalArgumentException {
    return numChildren(p) > 0;
}

@Override
public boolean isRoot(Position<E> p) throws IllegalArgumentException {
    return p == root();
}

Some methods like size(), numChildren() and root() are not implemented in this abstract class. Instead, they must be implemented by any concrete class that extends AbstractTree.java.

we add isEmpty() to know if the tree is empty.

Depth and height of a tree

Depth: The depth of a position p in a tree is the number of edges from the root to that node. It measures how far the p is from the root or the number of ancestors of p, other than p itself.
- If p is the root, then the depth of p is 0.
- Otherwise, the depth of p is one plus the depth of the parent of p

Add the following code to calculate the Depth of position p in AbstractTree.java.

public int depth(Position<E> p) {
    if (isRoot(p))
        return 0;
    else
        return 1 + depth(parent(p));
}

Height: The height of a tree is the longest path from the root to a leaf. A tree with only one position (just the root) has a height of 0.
Formally, we define the height of a position p in a tree T as follows:

• If p is a leaf, then the height of p is 0.
• Otherwise, the height of p is one more than the maximum of the heights ofp’s children.

Add the following code to calculate the Height of a Tree in AbstractTree.java.

public int height(Position<E> p) {
    int h = 0;
    for (Position<E> c : children(p)) {
        h = Math.max(h, 1 + height(c));
    }
    return h;
}

Iterator

To enable traversal and access of tree elements, we need to implement iterator functionality. Add the following code to the AbstractTree.java file.

 private class ElementIterator implements Iterator<E> {
    Iterator<Position<E>> posIterator = positions().iterator();

    @Override
    public boolean hasNext() {
        return posIterator.hasNext();
    }

    @Override
    public E next() {
        return posIterator.next().getElement();
    }

    public void remove() {
        posIterator.remove();
    }

}

@Override
public Iterator<E> iterator() {
    return new ElementIterator();
}

We create an inner class, ElementIterator, which implements the Iterator interface. (The Iterator interface is beyond the scope of this post; comment below if you'd like a dedicated explanation.)

The positions method, inside ElementIterator, lacks an implementation in AbstractTree.java. So, any concrete class inheriting from AbstractTree must provide its own implementation for this method.

Traversing

Time to Code!

Alright, code explorers! We've journeyed through the theoretical forests of tree traversals, understanding the ins and outs of Preorder, Postorder, Inorder, and Breadth-First approaches.

But let's be real, simply knowing about traversals is like having a fantastic recipe without ever stepping into the kitchen. So, in this section, we're finally going to get our hands gloriously dirty with the practical implementation! This is where the rubber meets the road, where those theories transform into actual, runnable Java code. Get ready to turn abstract concepts into concrete lines of Java. It's time to make our trees sing!

Preorder Traversal

Add the following code on AbstractTree.java

private void preorderSubtree(Position<E> p, List<Position<E>> snapshot) {
    snapshot.add(p);
    for (Position<E> c : children(p)) {
        preorderSubtree(c, snapshot);
    }
}

public Iterable<Position<E>> preorder() {
    List<Position<E>> snapshot = new ArrayList<>();
    if (!isEmpty())
        preorderSubtree(root(), snapshot);
    return snapshot;
}

💡 Here an ArrayList implement Iterable interface.

Postorder Traversal

Add the following code on AbstractTree.java

private void postorderSubtree(Position<E> p, List<Position<E>> snapshot) {
  for (Position<E> c : children(p)) {
      postorderSubtree(c, snapshot);
  }
  snapshot.add(p);
}

public Iterable<Position<E>> postorder() {
  List<Position<E>> snapshot = new ArrayList<>();
  if (!isEmpty())
      postorderSubtree(root(), snapshot);

  return snapshot;
}

Breadth-First Tree Traversal BFS

Add the following code on AbstractTree.java

public Iterable<Position<E>> breadthfirst() {
      List<Position<E>> snapshot = new ArrayList<>();
      if (!isEmpty()) {
          Queue<Position<E>> fring = new LinkedList<>();
          fring.add(root());
          while (fring.size() > 0) {
              Position<E> p = fring.remove();
              snapshot.add(p);
              for (Position<E> c : children(p)) {
                  fring.add(c);
              }
          }
      }

      return snapshot;
}

💡 Given that these traversal methods are universally adored by all tree types (they're just that versatile!), we'll be placing their implementation where they belong: directly within our AbstractTree class. Think of it as a one-stop shop for all your tree-walking needs.

import this packages

import java.util.ArrayList;
import java.util.List;

Binary Tree

💡 Let's talk about the binary tree – it's like the slightly more strict parent in the data structure family. It's still a hierarchical structure, but each node has a very clear rule: "You get at most two children, and they must be designated as either the 'left child' or the 'right child.'" No middle children, no more than two, thank you very much!

Now, within the binary tree world, we have our overachievers: the proper binary tree (also sometimes called a full binary tree). These are the nodes that really commit to the family plan. Every node in a proper binary tree has either zero children (the happily child-free nodes) or exactly two children (the ones who doubled down on parenting). So, if a node isn't a leaf, it's definitely a parent of twins.

Naturally, if a binary tree isn't following these strict twin-or-nothing rules, it's deemed improper. These are the nodes with just one child, perhaps sending their single offspring off to play alone while their proper cousins have a built-in playmate. They're not "wrong," just... less committed to the "full" family ideal.

The Binary Tree Abstract Data Type

left(p): Returns the position of the left child of p (or null if p has no left child).

right(p): Returns the position of the right child of p (or null if p has no right child).

sibling(p): Returns the position of the sibling of p (or null if p has no sibling).

Next, we will define an interface for this ADT. Create the BinaryTree.java file and add the following code:

public interface BinaryTree<E> extends Tree<E> {
    Position<E> left(Position<E> p) throws IllegalArgumentException;

    Position<E> right(Position<E> p) throws IllegalArgumentException;

    Position<E> sibling(Position<E> p) throws IllegalArgumentException;
}

Abstract Binary Tree

Next, we'll create an abstract class, AbstractBinaryTree, that serves as a base for all binary tree implementations. This class will include common methods like sibling(), children() and numChildren() . Create the AbstractBinaryTree.java file and add the following code:

import java.util.ArrayList;
import java.util.List;

public abstract class AbstractBinaryTree<E> extends AbstractTree<E> implements BinaryTree<E> {
        @Override
      public Position<E> sibling(Position<E> p) throws IllegalArgumentException {
          Position<E> parent = parent(p);
          if (parent == null)
              return null;
          if (p == left(parent))
              return right(parent);
          else
              return right(parent);
      }

      @Override
      public Iterable<Position<E>> children(Position<E> p) throws IllegalArgumentException {
          List<Position<E>> snapshot = new ArrayList<>(2);
          if (left(p) != null)
              snapshot.add(left(p));
          if (right(p) != null)
              snapshot.add(right(p));

          return snapshot;
      }

      @Override
    public int numChildren(Position<E> p) throws IllegalArgumentException {
        int count = 0;
        if (left(p) != null)
            count++;
        if (right(p) != null)
            count++;

        return count;
    }
}

Linked Binary Tree

A structure with a node that maintains references to the element stored at a position p and to the nodes associated with the children and parent of p. If p is the root of T, then the parent field of p is null.

Furthermore, each node within it holds reference nodes to its respective left and right child nodes.

Now that we've covered the definitions, it's time for implementation! Begin by creating LinkedBinaryTree.java and inserting the following code:

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {
        public LinkedBinaryTree() {
    }
}

Next, add this code in LinkedBinaryTree class.

 protected static class Node<E> implements Position<E> {
        private E element;
        private Node<E> parent;
        private Node<E> left;
        private Node<E> right;

        public Node(E element, Node<E> parent, Node<E> left, Node<E> right) {
            this.element = element;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        @Override
        public E getElement() throws IllegalStateException {
            return element;
        }

        public void setElement(E element) {
            this.element = element;
        }

        public Node<E> getParent() {
            return parent;
        }

        public void setParent(Node<E> parent) {
            this.parent = parent;
        }

        public Node<E> getLeft() {
            return left;
        }

        public void setLeft(Node<E> left) {
            this.left = left;
        }

        public Node<E> getRight() {
            return right;
        }

        public void setRight(Node<E> right) {
            this.right = right;
        }

    }

    protected Node<E> createNode(E e, Node<E> parent, Node<E> left, Node<E> right) {
        return new Node<E>(e, parent, left, right);
    }

    protected Node<E> root = null;
    private int size = 0;

Here we create an inner class Node that implements Position interface (defined previously). we also initialize the root and size of the tree. The method createNode is used to create a new instance of node.

Accessor Methods

Write the following code:

 protected Node<E> validate(Position<E> p) throws IllegalArgumentException {
    if (!(p instanceof Node))
        throw new IllegalArgumentException("Not valid position type");
    Node<E> node = (Node<E>) p;
    if (node.getParent() == node)
        throw new IllegalArgumentException("p is no longer in the tree");
    return node;
}

@Override
public Position<E> left(Position<E> p) throws IllegalArgumentException {
    Node<E> node = validate(p);
    return node.getLeft();
}

@Override
public Position<E> right(Position<E> p) throws IllegalArgumentException {
    Node<E> node = validate(p);
    return node.getRight();
}

@Override
public Position<E> root() {
    return root;
}

@Override
public Position<E> parent(Position<E> p) throws IllegalArgumentException {
    Node<E> node = validate(p);
    return node.getParent();
}

@Override
public int size() {
    return size;
}

we use validate method to verify if the position is an instance of Node and if the node exists.

Operative Methods

These methods facilitate operations such as adding, updating, and removing elements.

addRoot(e): Creates a root for an empty tree, storing e as the element, and returns the position of that root; an error occurs if the tree is not empty.

addLeft(p, e): Creates a left child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a left child.

addRight(p, e): Creates a right child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a right child.

set(p, e): Replaces the element stored at position p with element e, and returns the previously stored element.

remove(p): Removes the node at position p, replacing it with its child (if any), and returns the element that had been stored at p an error occurs if p has two children.

Let's implement the methods we just discussed. Insert the following code on LinkedBinaryTree.java class.

public Position<E> addRoot(E e) throws IllegalStateException {
    if (!isEmpty())
        throw new IllegalStateException("Tree is not empty");
    root = createNode(e, null, null, null);
    size = 1;
    return root;
}

public Position<E> addLeft(Position<E> p, E e) throws IllegalArgumentException {
    Node<E> parent = validate(p);
    if (parent.getLeft() != null)
        throw new IllegalArgumentException("p already has a left child");
    Node<E> child = createNode(e, parent, null, null);
    parent.setLeft(child);
    size++;

    return child;
}

public Position<E> addRight(Position<E> p, E e) throws IllegalArgumentException {
    Node<E> parent = validate(p);
    if (parent.getRight() != null)
        throw new IllegalArgumentException("p already has a right child");
    Node<E> child = createNode(e, parent, null, null);
    parent.setRight(child);
    size++;

    return child;
}

public E set(Position<E> p, E e) throws IllegalArgumentException {
    Node<E> node = validate(p);
    E temp = node.getElement();
    node.setElement(e);
    return temp;
}

 public E remove(Position<E> p) throws IllegalArgumentException {
    Node<E> node = validate(p);
    if (numChildren(p) == 2)
        throw new IllegalArgumentException("p has two children");
    Node<E> child = node.getLeft() != null ? node.getLeft() : node.getRight();

    if (child != null)
        child.setParent(node.getParent());
    if (node == root)
        root = child;
    else {
        Node<E> parent = node.getParent();
        if (node == parent.getLeft())
            parent.setLeft(child);
        else
            parent.setRight(child);
    }
    size--;
    E temp = node.getElement();
    node.setElement(null);
    node.setLeft(null);
    node.setRight(null);
    node.setParent(null);
    return temp;
}

Traversal

Since we've already implemented general tree traversal methods in AbstractTree.java, we will now focus specifically on inorder traversal. This is the primary traversal method used for binary trees. To implement inorder traversal, add the following code to the AbstractBinaryTree class:

private void inorderSubtree(Position<E> p, List<Position<E>> snapshot) {
    if (left(p) != null)
        inorderSubtree(left(p), snapshot);

    snapshot.add(p);
    if (right(p) != null)
        inorderSubtree(right(p), snapshot);
}

public List<Position<E>> inorder() {
    List<Position<E>> snapshot = new ArrayList<>();
    if (!isEmpty())
        inorderSubtree(root(), snapshot);
    return snapshot;
}

@Override
public Iterable<Position<E>> positions() {
    return inorder();
}

💡 The positions method is implemented here to ensure that inorder traversal serves as the default traversal method for the LinkedBinaryTree class. This method can be overridden to provide an alternative traversal implementation.

💡 With the tree implementation complete, it's time to test it out! Navigate to Main.java and insert this code into your main method

public static void main(String[] args) {
    LinkedBinaryTree<Integer> bi = new LinkedBinaryTree<>();

      Position<Integer> one = bi.addRoot(1);
      Position<Integer> left2 = bi.addLeft(one, 2);
      bi.addLeft(left2, 4);

      Position<Integer> right = bi.addRight(one, 3);
      bi.addRight(right, 6);

      bi.addRight(left2, 5);

      var pre = bi.preorder();

      for (Position<Integer> integer : pre) {
          System.out.print(integer.getElement() + ", ");
      }
      System.out.println();
      var post = bi.postorder();

      for (Position<Integer> integer : post) {
          System.out.print(integer.getElement() + ", ");
      }

      System.out.println();
      var bfs = bi.breadthfirst();
      for (Position<Integer> integer : bfs) {
          System.out.print(integer.getElement() + ", ");
      }

      System.out.println();
      var inorder = bi.positions();
      for (Position<Integer> integer : inorder) {
          System.out.print(integer.getElement() + ", ");
      }
}

Forem: Knitely

Graphs In Java (Part 2)

Introduction

Topological ordering

Weighted Graphs

Dijkstra’s Algorithm

Minimum Spanning Tree MST

Kruskal's algorithm

Prim's Algorithm

Graph In Java ☕

Introduction

Graph

Basic terms of a graph

The Vertex ADT

The Graph ADT

Graph representation

Adjacency List Implementation

Graph traversal algorithms

Depth-First Search (DFS)

Breadth-First Search (BFS)

HashMap in Java

Introduction

Map

The Map Interface

The AbstractMap.java class

The Hash Tables

Hash Function

Hash Codes

Compression Function

Collision Handling

Separate Chaining

Open Addressing

Linear Probing

Tree In Java ☕

Introduction

Welcome, Fellow Code Explorers!

Definition

External, internal node and many more

Traversal

Implementing Tree On Java ☕

Why "Position" is Better for Tree Nodes (and Its Catch)

Abstract Tree

The Tree Abstract Data Type

Depth and height of a tree

Iterator

Traversing

Time to Code!

Binary Tree

The Binary Tree Abstract Data Type

Abstract Binary Tree

Linked Binary Tree

Minimum Spanning Tree `MST`

The `AbstractMap.java` class