Repository: TheAlgorithms/Java
Pull request #6169 (2025-02-16 19:27:56)

Added Heavy-Light Decomposition (HLD) for Efficient Tree Queries
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

**Description:**
    This PR introduces an implementation of Heavy-Light Decomposition (HLD) in Java, enabling efficient path queries (such as maximum, sum, or updates) on a tree using segment trees. HLD reduces query time complexity from O(N) to O(log N) by decomposing the tree into heavy and light chains. Instead of traversing the whole tree (O(N)), we use HLD to jump chains and use segment trees for fast path queries in O(logN).

✅ Features:
1. Supports path queries (e.g., max in path, sum in path).
2. Uses segment trees for efficient range queries.
3. Optimized tree decomposition and traversal.

Example:
    Consider the below Tree 
```
       1 (10)
      /   \
   2 (20)  3 (30)
   /   \
4 (40)  5 (50)
```

Path Queries and Expected Results
-------------------------------------
1. Maximum in Path (4 → 5)
Path: 4 → 2 → 5
Values along the path: {40, 20, 50}
Max Value: 50

2. Maximum in Path (3 → 4)
Path: 3 → 1 → 2 → 4
Values along the path: {30, 10, 20, 40}
Max Value: 40

Note: Edges are added with indices to define the tree's structure, while node values are initialized separately. This separation allows for flexible updates and queries without altering the tree's topology, ensuring greater efficiency in handling updates and queries.

I have a strong passion for algorithms, particularly their efficiency, and am eager to contribute to this project. Let me know if any changes are needed! 🚀😊

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6169?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `95.45455%` with `4 lines` in your changes missing coverage. Please review.
> Project coverage is 74.08%. Comparing base [(`63ce6b8`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/63ce6b8ca57e99203dbc5129a50662d5cc48799e?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`e8829f0`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/e8829f035859777495bed502b95c4048579c37fd?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6169?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...om/thealgorithms/tree/HeavyLightDecomposition.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6169?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Ftree%2FHeavyLightDecomposition.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy90cmVlL0hlYXZ5TGlnaHREZWNvbXBvc2l0aW9uLmphdmE=) | 95.45% | [3 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6169?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #6169      +/-   ##
============================================
+ Coverage     73.97%   74.08%   +0.11%     
- Complexity     5157     5190      +33     
============================================
  Files           662      663       +1     
  Lines         17681    17769      +88     
  Branches       3407     3421      +14     
============================================
+ Hits          13079    13165      +86     
- Misses         4097     4100       +3     
+ Partials        505      504       -1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6169?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 6ccaf0b3..009de204 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -723,6 +723,8 @@
             * [WordLadder](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/strings/WordLadder.java)
             * zigZagPattern
               * [ZigZagPattern](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/strings/zigZagPattern/ZigZagPattern.java)
+          * tree
+            * [HeavyLightDecomposition](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/tree/HeavyLightDecomposition.java)
   * test
     * java
       * com
@@ -1367,3 +1369,5 @@
             * [WordLadderTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/strings/WordLadderTest.java)
             * zigZagPattern
               * [ZigZagPatternTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/strings/zigZagPattern/ZigZagPatternTest.java)
+          * tree
+            * [HeavyLightDecompositionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/tree/HeavyLightDecompositionTest.java)
diff --git a/src/main/java/com/thealgorithms/tree/HeavyLightDecomposition.java b/src/main/java/com/thealgorithms/tree/HeavyLightDecomposition.java
new file mode 100644
index 00000000..236a2320
--- /dev/null
+++ b/src/main/java/com/thealgorithms/tree/HeavyLightDecomposition.java
@@ -0,0 +1,157 @@
+package com.thealgorithms.tree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Heavy-Light Decomposition (HLD) implementation in Java.
+ * HLD is used to efficiently handle path queries on trees, such as maximum,
+ * sum, or updates. It decomposes the tree into heavy and light chains,
+ * enabling queries in O(log N) time.
+ * Wikipedia Reference: https://en.wikipedia.org/wiki/Heavy-light_decomposition
+ * Author: Nithin U.
+ * Github: https://github.com/NithinU2802
+ */
+
+public class HeavyLightDecomposition {
+    private List<List<Integer>> tree;
+    private int[] parent;
+    private int[] depth;
+    private int[] subtreeSize;
+    private int[] chainHead;
+    private int[] position;
+    private int[] nodeValue;
+    private int[] segmentTree;
+    private int positionIndex;
+
+    public HeavyLightDecomposition(int n) {
+        tree = new ArrayList<>();
+        for (int i = 0; i <= n; i++) {
+            tree.add(new ArrayList<>());
+        }
+        parent = new int[n + 1];
+        depth = new int[n + 1];
+        subtreeSize = new int[n + 1];
+        chainHead = new int[n + 1];
+        position = new int[n + 1];
+        nodeValue = new int[n + 1];
+        segmentTree = new int[4 * (n + 1)];
+        for (int i = 0; i <= n; i++) {
+            chainHead[i] = -1;
+        }
+        positionIndex = 0;
+    }
+
+    public int getPosition(int index) {
+        return position[index];
+    }
+
+    public int getPositionIndex() {
+        return positionIndex;
+    }
+
+    public void addEdge(int u, int v) {
+        tree.get(u).add(v);
+        tree.get(v).add(u);
+    }
+
+    private void dfsSize(int node, int parentNode) {
+        parent[node] = parentNode;
+        subtreeSize[node] = 1;
+        for (int child : tree.get(node)) {
+            if (child != parentNode) {
+                depth[child] = depth[node] + 1;
+                dfsSize(child, node);
+                subtreeSize[node] += subtreeSize[child];
+            }
+        }
+    }
+
+    private void decompose(int node, int head) {
+        chainHead[node] = head;
+        position[node] = positionIndex++;
+        int heavyChild = -1;
+        int maxSubtreeSize = -1;
+        for (int child : tree.get(node)) {
+            if (child != parent[node] && subtreeSize[child] > maxSubtreeSize) {
+                heavyChild = child;
+                maxSubtreeSize = subtreeSize[child];
+            }
+        }
+        if (heavyChild != -1) {
+            decompose(heavyChild, head);
+        }
+        for (int child : tree.get(node)) {
+            if (child != parent[node] && child != heavyChild) {
+                decompose(child, child);
+            }
+        }
+    }
+
+    private void buildSegmentTree(int node, int start, int end) {
+        if (start == end) {
+            segmentTree[node] = nodeValue[start];
+            return;
+        }
+        int mid = (start + end) / 2;
+        buildSegmentTree(2 * node, start, mid);
+        buildSegmentTree(2 * node + 1, mid + 1, end);
+        segmentTree[node] = Math.max(segmentTree[2 * node], segmentTree[2 * node + 1]);
+    }
+
+    public void updateSegmentTree(int node, int start, int end, int index, int value) {
+        if (start == end) {
+            segmentTree[node] = value;
+            return;
+        }
+        int mid = (start + end) / 2;
+        if (index <= mid) {
+            updateSegmentTree(2 * node, start, mid, index, value);
+        } else {
+            updateSegmentTree(2 * node + 1, mid + 1, end, index, value);
+        }
+        segmentTree[node] = Math.max(segmentTree[2 * node], segmentTree[2 * node + 1]);
+    }
+
+    public int querySegmentTree(int node, int start, int end, int left, int right) {
+        if (left > end || right < start) {
+            return Integer.MIN_VALUE;
+        }
+        if (left <= start && end <= right) {
+            return segmentTree[node];
+        }
+        int mid = (start + end) / 2;
+        int leftQuery = querySegmentTree(2 * node, start, mid, left, right);
+        int rightQuery = querySegmentTree(2 * node + 1, mid + 1, end, left, right);
+        return Math.max(leftQuery, rightQuery);
+    }
+
+    public int queryMaxInPath(int u, int v) {
+        int result = Integer.MIN_VALUE;
+        while (chainHead[u] != chainHead[v]) {
+            if (depth[chainHead[u]] < depth[chainHead[v]]) {
+                int temp = u;
+                u = v;
+                v = temp;
+            }
+            result = Math.max(result, querySegmentTree(1, 0, positionIndex - 1, position[chainHead[u]], position[u]));
+            u = parent[chainHead[u]];
+        }
+        if (depth[u] > depth[v]) {
+            int temp = u;
+            u = v;
+            v = temp;
+        }
+        result = Math.max(result, querySegmentTree(1, 0, positionIndex - 1, position[u], position[v]));
+        return result;
+    }
+
+    public void initialize(int root, int[] values) {
+        dfsSize(root, -1);
+        decompose(root, root);
+        for (int i = 0; i < values.length; i++) {
+            nodeValue[position[i]] = values[i];
+        }
+        buildSegmentTree(1, 0, positionIndex - 1);
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/tree/HeavyLightDecompositionTest.java b/src/test/java/com/thealgorithms/tree/HeavyLightDecompositionTest.java
new file mode 100644
index 00000000..29189290
--- /dev/null
+++ b/src/test/java/com/thealgorithms/tree/HeavyLightDecompositionTest.java
@@ -0,0 +1,69 @@
+package com.thealgorithms.tree;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+class HeavyLightDecompositionTest {
+
+    private HeavyLightDecomposition hld;
+    private final int[] values = {0, 10, 20, 30, 40, 50};
+
+    /**
+     * Initializes the test environment with a predefined tree structure and values.
+     */
+    @BeforeEach
+    void setUp() {
+        hld = new HeavyLightDecomposition(5);
+        hld.addEdge(1, 2);
+        hld.addEdge(1, 3);
+        hld.addEdge(2, 4);
+        hld.addEdge(2, 5);
+        hld.initialize(1, values);
+    }
+
+    /**
+     * Verifies that the tree initializes successfully without errors.
+     */
+    @Test
+    void testBasicTreeInitialization() {
+        assertTrue(true, "Basic tree structure initialized successfully");
+    }
+
+    /**
+     * Tests the maximum value query in the path between nodes.
+     */
+    @Test
+    void testQueryMaxInPath() {
+        assertEquals(50, hld.queryMaxInPath(4, 5), "Max value in path (4,5) should be 50");
+        assertEquals(30, hld.queryMaxInPath(3, 2), "Max value in path (3,2) should be 30");
+    }
+
+    /**
+     * Tests updating a node's value and ensuring it is reflected in queries.
+     */
+    @Test
+    void testUpdateNodeValue() {
+        hld.updateSegmentTree(1, 0, hld.getPositionIndex() - 1, hld.getPosition(4), 100);
+        assertEquals(100, hld.queryMaxInPath(4, 5), "Updated value should be reflected in query");
+    }
+
+    /**
+     * Tests the maximum value query in a skewed tree structure.
+     */
+    @Test
+    void testSkewedTreeMaxQuery() {
+        assertEquals(40, hld.queryMaxInPath(1, 4), "Max value in skewed tree (1,4) should be 40");
+    }
+
+    /**
+     * Ensures query handles cases where u is a deeper node correctly.
+     */
+    @Test
+    void testDepthSwapInPathQuery() {
+        assertEquals(50, hld.queryMaxInPath(5, 2), "Query should handle depth swap correctly");
+        assertEquals(40, hld.queryMaxInPath(4, 1), "Query should handle swapped nodes correctly and return max value");
+    }
+}