Skip to main content
Mapagam

Implementing Advanced Tree Techniques

1. Implementing Centroid Decomposition

Centroid decomposition is a powerful technique for breaking down trees into smaller components, allowing efficient handling of queries and updates on tree structures.

Operation Description Time Complexity Space Complexity
Find Centroid Rooted tree's centroid is the node whose removal splits the tree into subtrees of size at most n/2. O(n) O(n)
Decompose Tree Recursively decompose the tree by removing centroids and processing remaining subtrees. O(n log n) O(n)

Example: Finding Centroid in a Tree

function findCentroid(tree) {
  const sizes = new Array(tree.nodes).fill(0);
  const parent = new Array(tree.nodes).fill(-1);

  // Compute subtree sizes
  function dfs(node, par) {
    sizes[node] = 1;
    for (const child of tree.children(node)) {
      if (child !== par) {
        parent[child] = node;
        dfs(child, node);
        sizes[node] += sizes[child];
      }
    }
  }

  dfs(0, -1);

  // Find centroid
  function isCentroid(node) {
    let maxSubtree = 0;
    for (const child of tree.children(node)) {
      if (child !== parent[node]) {
        maxSubtree = Math.max(maxSubtree, sizes[child]);
      }
    }
    return maxSubtree <= Math.floor(tree.nodes / 2);
  }

  for (let i = 0; i < tree.nodes; i++) {
    if (isCentroid(i)) return i;
  }
  return -1;
}
Note: Centroid decomposition is useful for problems involving path queries or updates on trees, such as finding the k-th node on a path or maintaining subtree statistics.

Key Steps in Centroid Decomposition

  • Find the centroid of the current tree.
  • Remove the centroid to form a forest of subtrees.
  • Recursively apply decomposition to each subtree.
  • Process queries or updates using the centroid tree structure.

2. Implementing Heavy-Light Decomposition

Heavy-Light Decomposition (HLD) is a tree decomposition technique used to efficiently handle queries on trees, such as path queries and subtree queries. It partitions the tree into disjoint paths such that each path is heavy or light, based on the size of subtrees.

Component Description Notes
Heavy Child The child with the largest subtree size in a node's children Each node has at most one heavy child
Light Child All other children of a node Each node can have multiple light children
Heavy Path A path formed by following heavy edges from a node to its descendants Each path is a continuous sequence of heavy edges
Light Edge An edge connecting a node to its light child Light edges break heavy paths

Example: Basic HLD Setup

class HLD {
  constructor(tree) {
    this.tree = tree;
    this.n = tree.length;
    this.parent = new Array(this.n).fill(-1);
    this.depth = new Array(this.n).fill(0);
    this.subtreeSize = new Array(this.n).fill(0);
    this.heavyChild = new Array(this.n).fill(-1);
    this.pathRoot = new Array(this.n).fill(-1);
    this.positionInPath = new Array(this.n).fill(0);
  }

  dfs(node, par) {
    this.parent[node] = par;
    this.subtreeSize[node] = 1;

    let maxSubtree = -1;
    let heavyChild = -1;

    for (let child of this.tree[node]) {
      if (child !== par) {
        this.depth[child] = this.depth[node] + 1;
        this.dfs(child, node);
        this.subtreeSize[node] += this.subtreeSize[child];
        if (this.subtreeSize[child] > maxSubtree) {
          maxSubtree = this.subtreeSize[child];
          heavyChild = child;
        }
      }
    }

    this.heavyChild[node] = heavyChild;
  }

  decompose(node, pathRoot) {
    this.pathRoot[node] = pathRoot;
    if (this.heavyChild[node] !== -1) {
      this.decompose(this.heavyChild[node], pathRoot);
    }

    for (let child of this.tree[node]) {
      if (child !== this.parent[node] && child !== this.heavyChild[node]) {
        this.decompose(child, child);
      }
    }
  }

  init() {
    this.dfs(0, -1);
    this.decompose(0, 0);
  }
}

Example: Path Query

function queryPath(u, v) {
  let result = 0;
  while (this.pathRoot[u] !== this.pathRoot[v]) {
    if (this.depth[this.pathRoot[u]] < this.depth[this.pathRoot[v]]) {
      [u, v] = [v, u];
    }
    result += querySegment(this.pathRoot[u], this.positionInPath[u]);
    u = this.parent[this.pathRoot[u]];
  }

  if (this.depth[u] > this.depth[v]) {
    [u, v] = [v, u];
  }

  result += querySegment(this.positionInPath[u], this.positionInPath[v]);
  return result;
}
Note: HLD is particularly useful in problems involving path updates and queries, such as finding the maximum element on a path or updating values along a path. The decomposition allows for efficient segment tree operations on paths.

A Link-Cut Tree (LCT) is a dynamic tree data structure that supports efficient operations on trees with dynamic changes, such as link and cut operations, and path queries. It is particularly useful in problems involving dynamic trees where the structure of the tree can change over time.

Operation Description Time Complexity Notes
makeTree Initializes a new tree with a single node O(1) Creates a new node in the tree structure
link Links two nodes in the tree, making one a child of another O(log n) Requires the nodes to be in different trees
cut Removes an edge from the tree, splitting it into two trees O(log n) Can only cut edges that are part of the tree structure
lca Finds the lowest common ancestor of two nodes O(log n) Assumes nodes are in the same tree
pathQuery Performs a query on the path between two nodes O(log n) Can be used for sum, max, min, etc. on path
pathUpdate Updates values along the path between two nodes O(log n) Supports lazy propagation for efficiency 
class Node {
  constructor(value) {
    this.value = value;
    this.parent = null;
    this.child = null;
    this.sibling = null;
    this.size = 1;
    this.isRoot = true;
  }
}

class LinkCutTree {
  constructor() {
    this.nodes = new Map();
  }

  makeTree(value) {
    const node = new Node(value);
    this.nodes.set(value, node);
    return node;
  }

  link(parent, child) {
    // Implementation of linking two nodes in the tree
    // This is a simplified version for illustrative purposes
    child.parent = parent;
    child.isRoot = false;
  }

  cut(node) {
    // Implementation of cutting a node from its parent
    if (node.parent) {
      node.parent = null;
      node.isRoot = true;
    }
  }

  lca(u, v) {
    // Implementation of finding lowest common ancestor
    // This is a simplified version for illustrative purposes
    return u.parent === v.parent ? u.parent : null;
  }

  pathQuery(u, v) {
    // Implementation of querying the path between u and v
    // This is a simplified version for illustrative purposes
    return u.value + v.value;
  }
}

// Example usage:
const lct = new LinkCutTree();
const nodeA = lct.makeTree(10);
const nodeB = lct.makeTree(20);
lct.link(nodeA, nodeB);
console.log(lct.lca(nodeA, nodeB)); // Example output
Note: The actual implementation of Link-Cut Trees involves complex rotations and splay operations to maintain balance and ensure efficient amortized time complexity. The example above is a simplified representation for clarity.
  • Dynamic Tree Operations: Efficiently supports link and cut operations
  • Path Queries: Fast path queries and updates using splay trees
  • Amortized Efficiency: Amortized O(log n) time for operations
  • Applications: Useful in problems involving dynamic trees, such as maintaining a forest of trees under changes

4. Solving Tree Path Queries

Query Type Description Approach Time Complexity
Path Sum Find if a path from root to leaf sums to a target value DFS with running sum, backtrack if needed O(n)
Lowest Common Ancestor (LCA) Find the deepest node that is an ancestor of two given nodes Binary lifting or Euler Tour + RMQ O(log n) per query after preprocessing
Kth Ancestor Find the kth ancestor of a node in tree Binary lifting with precomputed ancestors O(log n) per query after O(n log n) preprocessing
Maximum Path Sum Find maximum sum of any path in the tree (can start and end at any node) Post-order DFS with global max tracking O(n)

Example: Path Sum

function hasPathSum(root, targetSum) {
    if (!root) return false;
    if (!root.left && !root.right) return root.val === targetSum;
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}

Example: Maximum Path Sum

let maxSum = -Infinity;

function maxPathSum(root) {
    if (!root) return 0;
    const left = Math.max(maxPathSum(root.left), 0);
    const right = Math.max(maxPathSum(root.right), 0);
    maxSum = Math.max(maxSum, left + right + root.val);
    return Math.max(left, right) + root.val;
}
Note: For LCA queries, binary lifting is efficient for multiple queries on static trees.

Path Query Techniques Summary

  • DFS-based approaches for path sums and max paths
  • Binary lifting for fast ancestor queries
  • Euler Tour + Segment Tree for range queries on paths

5. Implementing Euler Tour Technique

The Euler Tour Technique is a powerful method for transforming tree problems into array-based problems, enabling efficient range queries and updates using data structures like segment trees or binary indexed trees.

Operation Description Time Complexity Space Complexity
Euler Tour Traversal Visit each node in a specific order: enter node, explore children, return to node O(n) O(n)
Range Query Query sum, min, max over a subtree or path O(log n) O(1)
Update Operation Modify value of a node and propagate changes O(log n) O(1)

Example: Euler Tour Traversal

class TreeNode {
  constructor(val, children = []) {
    this.val = val;
    this.children = children;
  }
}

function eulerTour(root) {
  const tour = [];
  
  function dfs(node) {
    tour.push(node.val);
    for (const child of node.children) {
      dfs(child);
    }
    tour.push(node.val);
  }

  dfs(root);
  return tour;
}

// Example usage:
const root = new TreeNode(1, [
  new TreeNode(2, [new TreeNode(4), new TreeNode(5)]),
  new TreeNode(3, [new TreeNode(6)])
]);

console.log(eulerTour(root)); // [1, 2, 4, 2, 5, 2, 1, 3, 6, 3, 1]

Example: Subtree Sum Query

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 0, 0, this.n - 1);
  }

  build(arr, node, start, end) {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      this.build(arr, 2 * node + 1, start, mid);
      this.build(arr, 2 * node + 2, mid + 1, end);
      this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
    }
  }

  query(node, start, end, l, r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.tree[node];
    const mid = Math.floor((start + end) / 2);
    return this.query(2 * node + 1, start, mid, l, r) +
           this.query(2 * node + 2, mid + 1, end, l, r);
  }

  update(node, start, end, idx, val) {
    if (start === end) {
      this.tree[node] = val;
    } else {
      const mid = Math.floor((start + end) / 2);
      if (idx <= mid) {
        this.update(2 * node + 1, start, mid, idx, val);
      } else {
        this.update(2 * node + 2, mid + 1, end, idx, val);
      }
      this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
    }
  }
}

// Example usage:
const tour = [1, 2, 4, 2, 5, 2, 1, 3, 6, 3, 1];
const segTree = new SegmentTree(tour);
console.log(segTree.query(0, 0, tour.length - 1, 0, 2)); // Sum of first three elements
Note: The Euler Tour Technique is particularly useful for problems involving path queries or subtree operations in trees. It allows converting tree problems into array problems, which can then be solved efficiently using standard data structures.

6. Finding Lowest Common Ancestor

Approach Description Time Complexity Space Complexity
Parent Pointer Each node stores a reference to its parent. Traverse upward from both nodes until a common ancestor is found. O(h) O(h)
Path to Root Find paths from both nodes to root, then compare paths to find LCA. O(h) O(h)
Binary Lifting Precompute ancestors at powers of two. Use binary search to find LCA efficiently. O(log h) O(h log h)
DFS with Post-order Use post-order traversal to find LCA during tree traversal. O(n) O(h)

Example: Binary Lifting Implementation

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function buildLCAArray(root) {
  const parent = new Map();
  const depth = new Map();
  const up = new Map();

  function dfs(node, par, d) {
    parent.set(node, par);
    depth.set(node, d);
    up.set(node, []);

    if (par) {
      up.get(node).push(par);
      let u = par;
      let pow = 1;
      while (up.get(u).length >= pow) {
        up.get(node).push(up.get(u)[pow - 1]);
        pow++;
      }
    }

    if (node.left) dfs(node.left, node, d + 1);
    if (node.right) dfs(node.right, node, d + 1);
  }

  dfs(root, null, 0);

  function findLCA(a, b) {
    if (depth.get(a) < depth.get(b)) [a, b] = [b, a];

    let diff = depth.get(a) - depth.get(b);
    while (diff > 0) {
      const pow = Math.floor(Math.log2(diff));
      a = up.get(a)[pow];
      diff -= 1 << pow;
    }

    if (a === b) return a;

    for (let i = up.get(a).length - 1; i >= 0; i--) {
      if (up.get(a)[i] !== up.get(b)[i]) {
        a = up.get(a)[i];
        b = up.get(b)[i];
      }
    }

    return parent.get(a);
  }

  return { findLCA };
}

Example: Path to Root Approach

function findLCAPath(root, p, q) {
  function findPath(node, target, path) {
    if (!node) return false;
    path.push(node);
    if (node === target) return true;
    if (findPath(node.left, target, path) || findPath(node.right, target, path)) {
      return true;
    }
    path.pop();
    return false;
  }

  const pathP = [];
  const pathQ = [];

  if (!findPath(root, p, pathP) || !findPath(root, q, pathQ)) return null;

  let i = 0;
  while (i < pathP.length && i < pathQ.length && pathP[i] === pathQ[i]) {
    i++;
  }

  return pathP[i - 1];
}
Note: Binary lifting is most efficient for multiple queries on the same tree.

When to Use Each Method

  • Parent Pointer: When nodes have parent references and queries are infrequent.
  • Path to Root: Simple implementation for small trees or one-time queries.
  • Binary Lifting: For frequent queries on large trees with pre-processing cost.
  • DFS Post-order: When traversing the tree anyway and LCA is needed.

7. Implementing Tree Flattening

Tree flattening is the process of converting a hierarchical tree structure into a linear list or array. This technique is useful for traversal, serialization, and simplifying operations on tree data structures.

Method Description Time Complexity Space Complexity
Breadth-First Search (BFS) Traverses nodes level by level using a queue. O(n) O(w)
Depth-First Search (DFS) - Pre-order Visits nodes in root-left-right order recursively or iteratively. O(n) O(h)
In-order DFS Visits nodes in left-root-right order (for binary trees). O(n) O(h)
Post-order DFS Visits nodes in left-right-root order (for binary trees). O(n) O(h)

Example: BFS Flattening

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function flattenBFS(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];
  
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.val);
    
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  
  return result;
}

// Example usage:
const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(flattenBFS(root)); // [1, 2, 3]

Example: DFS Pre-order Flattening

function flattenDFS(root) {
  const result = [];
  
  function dfs(node) {
    if (!node) return;
    
    result.push(node.val);
    dfs(node.left);
    dfs(node.right);
  }
  
  dfs(root);
  return result;
}

// Example usage:
const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(flattenDFS(root)); // [1, 2, 3]
Note: For in-order and post-order flattening, the order of elements depends on the specific traversal type. These methods are particularly useful for binary trees.

8. Solving Subtree Queries

Query Type Description Time Complexity Space Complexity
Sum of Subtree Values Calculate sum of all node values in a subtree rooted at a given node O(1) with precomputed sums O(n)
Count of Nodes in Subtree Count total nodes in a subtree rooted at a given node O(1) with precomputed counts O(n)
Maximum Value in Subtree Find maximum value among all nodes in a subtree O(1) with precomputed max O(n)

Example: Precomputed Subtree Sums

class TreeNode {
  constructor(val, children = []) {
    this.val = val;
    this.children = children;
    this.subtreeSum = 0;
  }
}

function computeSubtreeSums(node) {
  if (!node) return 0;
  
  let sum = node.val;
  for (const child of node.children) {
    sum += computeSubtreeSums(child);
  }
  
  node.subtreeSum = sum;
  return sum;
}

// Example usage:
const root = new TreeNode(1, [
  new TreeNode(2, [new TreeNode(4), new TreeNode(5)]),
  new TreeNode(3, [new TreeNode(6)])
]);

computeSubtreeSums(root);
console.log(root.subtreeSum); // 21 (1+2+3+4+5+6)
console.log(root.children[0].subtreeSum); // 11 (2+4+5)

Example: Range Query on Tree

class TreeWithRangeQuery {
  constructor(nodes) {
    this.nodes = nodes;
    this.inOrder = [];
    this.outOrder = [];
    this.time = 0;
  }

  dfs(node, parent) {
    this.inOrder[node.id] = ++this.time;
    for (const child of node.children) {
      if (child !== parent) {
        this.dfs(child, node);
      }
    }
    this.outOrder[node.id] = ++this.time;
  }

  querySubtree(nodeId) {
    const inStart = this.inOrder[nodeId];
    const outEnd = this.outOrder[nodeId];
    // Use segment tree or BIT to query range [inStart, outEnd]
    return `Range query for subtree rooted at ${nodeId}`;
  }
}

// Example usage:
const tree = new TreeWithRangeQuery([
  { id: 1, val: 10 },
  { id: 2, val: 5 },
  { id: 3, val: 15 }
]);

// Build in-order and out-order times
tree.dfs(tree.nodes[0], null);
console.log(tree.querySubtree(1)); // Range query for subtree rooted at 1
Note: For efficient subtree queries, consider using Euler Tour Technique or Heavy-Light Decomposition depending on query patterns and update frequency.

9. Implementing Virtual Tree

Feature Description Implementation
Virtual Tree A tree structure that is not fully materialized in memory, often used to represent hierarchical data with lazy loading. 
class VirtualTree {
  constructor(data) {
    this.data = data;
  }

  getNode(id) {
    return this.data[id];
  }

  getChildren(node) {
    return node.children || [];
  }
}

Example: Virtual Tree Node Access

const tree = new VirtualTree({
  "root": {
    id: "root",
    value: "Root Node",
    children: ["child1", "child2"]
  },
  "child1": {
    id: "child1",
    value: "Child 1",
    children: []
  },
  "child2": {
    id: "child2",
    value: "Child 2",
    children: ["grandchild"]
  },
  "grandchild": {
    id: "grandchild",
    value: "Grandchild",
    children: []
  }
});

console.log(tree.getNode("root").value); // "Root Node"
console.log(tree.getChildren(tree.getNode("child2"))); // ["grandchild"]
Note: Virtual trees are useful for managing large hierarchical datasets where full materialization is inefficient.

Key Concepts

  • Lazy loading of nodes
  • Memory-efficient representation
  • Dynamic traversal and querying

10. Finding Tree Isomorphism

Tree isomorphism determines whether two trees have the same structure and node values, regardless of how they are labeled or arranged.

Property Description Notes
Structural Isomorphism Two trees are structurally isomorphic if they have the same shape and node values. Requires matching tree structures recursively
Labelled Isomorphism Two trees are isomorphic if they have the same structure and node labels. Label matching must be preserved

Example: Tree Isomorphism Check

class TreeNode {
  constructor(val, children = []) {
    this.val = val;
    this.children = children;
  }
}

function areTreesIsomorphic(tree1, tree2) {
  if (!tree1 && !tree2) return true;
  if (!tree1 || !tree2) return false;

  if (tree1.val !== tree2.val) return false;

  const children1 = tree1.children;
  const children2 = tree2.children;

  if (children1.length !== children2.length) return false;

  // Sort children by their structure to compare isomorphism
  const sorted1 = children1.sort((a, b) => a.val - b.val);
  const sorted2 = children2.sort((a, b) => a.val - b.val);

  for (let i = 0; i < sorted1.length; i++) {
    if (!areTreesIsomorphic(sorted1[i], sorted2[i])) return false;
  }

  return true;
}

// Example usage:
const tree1 = new TreeNode(1, [new TreeNode(2), new TreeNode(3)]);
const tree2 = new TreeNode(1, [new TreeNode(3), new TreeNode(2)]);

console.log(areTreesIsomorphic(tree1, tree2)); // true
Note: For labeled trees, node values must also match in addition to structure.

Key Concepts

  • Isomorphism implies structural and value equivalence
  • Can be checked recursively using tree traversal
  • Sorting children by value helps in comparison

11. Implementing Rerooting Technique

The rerooting technique is a powerful algorithmic approach used to efficiently solve problems on trees by transforming the tree structure to allow for fast updates and queries. It is particularly useful in dynamic tree problems where we need to handle operations like subtree updates or path queries.

Operation Description Time Complexity Space Complexity
Reroot Tree Recompute tree properties when root changes O(n) O(n)
Subtree Updates Update values in a subtree rooted at a node O(1) per update O(n)
Path Queries Query values along a path between two nodes O(log n) O(n)

Example: Rerooting for Subtree Sum Queries

class Tree {
  constructor(n) {
    this.n = n;
    this.children = Array(n).fill().map(() => []);
    this.subtreeSum = Array(n).fill(0);
    this.parent = Array(n).fill(-1);
  }

  addEdge(u, v) {
    this.children[u].push(v);
    this.children[v].push(u);
  }

  reroot(root) {
    // Compute subtree sums starting from root
    this.dfs(root, -1);
  }

  dfs(node, parent) {
    this.subtreeSum[node] = node; // Example: node value is its index
    for (let child of this.children[node]) {
      if (child !== parent) {
        this.dfs(child, node);
        this.subtreeSum[node] += this.subtreeSum[child];
      }
    }
  }

  getSubtreeSum(node) {
    return this.subtreeSum[node];
  }
}

// Example usage:
const tree = new Tree(5);
tree.addEdge(0, 1);
tree.addEdge(0, 2);
tree.addEdge(1, 3);
tree.addEdge(1, 4);

tree.reroot(0); // Root the tree at node 0
console.log(tree.getSubtreeSum(1)); // Sum of subtree rooted at node 1
Note: The rerooting technique is often used in combination with centroid decomposition or heavy-light decomposition to handle more complex queries efficiently.

Key Concepts in Rerooting

  • Subtree Computation: Efficiently compute properties for each subtree.
  • Root Change: Re-rooting allows for dynamic updates without full recomputation.
  • Dynamic Queries: Handle queries on paths or subtrees in logarithmic time.

Was this article helpful?

Related Cheat Sheets