2509. Cycle Length Queries in a Tree

HardTreeBinary Tree
Leetcode Link

Problem Description

You are given a virtual complete binary tree that contains 2^n - 1 nodes, where n is an integer. Each node in this tree is assigned a unique value, and the root node starts with value 1. For any node in the tree that has a value val, you can always find its children by following these rules:

  • The left child will have the value 2 * val.
  • The right child will have the value 2 * val + 1.

In addition to the binary tree, you are presented with a list of queries. Each query is a pair of integers [a_i, b_i] representing nodes in the tree. For each query, you are expected to:

  1. Add an edge directly connecting the nodes labeled a_i and b_i.
  2. Determine the length of the cycle that includes this new edge.
  3. Remove the edge you added between a_i and b_i.

Note that a cycle in a graph is defined as a closed path where the starting and ending nodes are identical and no edge is traversed more than once. The length of this cycle is considered the total number of edges within that cycle.

Your task is to process all the queries and return an array of integers, each representing the length of the cycle that would be formed by adding the edge specified in the corresponding query.

Intuition

Since we are working with a complete binary tree, we can take advantage of its properties to calculate the distance between two nodes. The properties of a binary tree let us know that any node val in the tree has its descendants determined by multiplication by 2 for the left child or multiplication by 2 and adding 1 for the right child.

The intuition behind the solution for determining the cycle length for a pair of nodes (a, b) is based on finding their lowest common ancestor (LCA). The lowest common ancestor of two nodes in a binary tree is the deepest (or highest-level) node that has both a and b as descendants (where we allow a node to be a descendant of itself).

Since we are adding an edge between nodes a and b, the cycle length would be equal to the distance from a to the LCA plus the distance from b to the LCA plus 1 (the added edge itself).

The algorithm starts by setting a counter t to 1, representing the added edge. Next, we iterate while a does not equal b - effectively, we are moving a and b up the tree towards the root until they meet, which would be at their LCA:

  • If a > b, we move a up to its parent, which is calculated by a >>= 1 (this is a bitwise right shift which is equivalent to dividing by 2).
  • If b > a, we do the same for b.
  • After each move, we increment the counter t.

Once a equals b, we have found the LCA and thus the cycle. The length of the cycle is the value stored in t at this point. We append the value of t to our ans list, which will eventually contain the answer for each query.

Learn more about Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The solution provided is straightforward and leverages the binary nature of the tree to efficiently find the lengths of cycles for each query. The data structure used is simply the tree modeled by the rules of the complete binary tree, and no additional complex data structures are required. The algorithm utilizes a while loop and bitwise operations to navigate the tree. Let's break down the steps and the patterns used:

  1. Initialization: The solution initializes an empty list ans which will store the lengths of cycles for each query.

  2. Processing Queries: The solution iterates over each query (a, b) within the queries list.

  3. Moving Up the Tree: Within a while loop, where the condition is a != b, the algorithm compares the values of a and b.

    • If a > b, it means that a is further down the tree. To move a up the tree (towards the root), the operation a >>= 1 is applied, which is a right bitwise shift equivalent to integer division by 2 — this moves a to its parent node.
    • If b > a, the same process is applied to b using a right bitwise shift.

  4. Counting Edges: Each time either a or b moves up the tree towards their lowest common ancestor (LCA), the counter t is incremented, since this represents traversing one edge towards the LCA for each node.

  5. Calculating Cycle Length: Once a and b are equal—meaning the LCA has been reached—the value in t now represents the total number of edges traversed, plus 1 for the edge that was added between a and b initially.

  6. Recording Results: The current length of the cycle is appended to the ans list.

  7. Returning Results: After all queries have been processed, the ans list is returned, which contains the calculated cycle length for each query.

By using bitwise shifts and a simple counter, the algorithm avoids any complicated traversal or search methods. This takes advantage of the inherent properties of a binary tree and results in an efficient O(log n) time complexity for finding the LCA and cycle length per query, where n is the total number of nodes in the tree. Hence, the overall time complexity of the solution depends on the number of queries m and is O(m log n).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's consider a small example with a binary tree of 2^3 - 1 = 7 nodes and a single query [4, 5]. The nodes in this binary tree would be numbered from 1 to 7 with the following structure:

1     1
2   /   \
3  2     3
4 / \   / \
54   5 6   7

Here's the step-by-step breakdown using our solution approach for the query [4, 5]:

  1. Initialization: Start with an empty list ans to store the lengths of cycles for the queries.

  2. Processing the Query [4, 5]: We consider the pair (a, b) where a = 4 and b = 5.

  3. Moving Up the Tree:

    • Initially, a = 4 and b = 5. Since a < b, we move b up the tree. Applying b >>= 1 changes b to 5 >> 1, which equals 2. We increase our counter t by 1.
    • Now a = 4 and b = 2. Since a > b, we move a up the tree. Applying a >>= 1 changes a to 4 >> 1, which equals 2. We increase our counter t by 1.

  4. Counting Edges:

    • At this point, after moving both a and b up the tree by one step each, our counter t is 3 because we started with 1 for the added edge, plus one increment for each of a and b.

  5. Calculating Cycle Length:

    • Now, since a equals b (a = 2 and b = 2), we have found the lowest common ancestor (LCA), which is node 2.

  6. Recording Results:

    • We append the current counter t value, which is 3, to our ans list. It signifies the cycle length for the query [4, 5] because it includes one step from 4 to 2, one step from 5 to 2, and one for the direct edge we added between 4 and 5.

  7. Returning Results:

    • After processing the query, the ans list contains [3], which represents the cycle length created by adding an edge between the nodes 4 and 5.

So for the query [4, 5], the algorithm would output [3], indicating that the cycle formed by adding an edge between node 4 and 5 has a length of three edges.

Solution Implementation

1from typing import List
2
3class Solution:
4    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
5        # Initialize an empty list to store the answer for each query
6        results = []
7      
8        # Iterate through each query in the list of queries
9        for query in queries:
10            # Extract the starting and ending nodes from the query
11            start_node, end_node = query
12          
13            # Initialize the cycle length variable to 1 (since the start and end nodes are counted as a step)
14            cycle_length = 1
15          
16            # Continue looping until the start node and end node are the same
17            while start_node != end_node:
18                # If the start node has a greater value, divide it by 2 (essentially moving up one level in the binary tree)
19                if start_node > end_node:
20                    start_node >>= 1
21                # Otherwise, if the end node has a greater value, divide it by 2
22                else:
23                    end_node >>= 1
24              
25                # Increment the cycle length with each step taken
26                cycle_length += 1
27          
28            # Append the calculated cycle length to the results list
29            results.append(cycle_length)
30      
31        # Return the list of results after all queries have been processed
32        return results
33
1class Solution {
2    public int[] cycleLengthQueries(int n, int[][] queries) {
3        // m represents the length of the queries array
4        int m = queries.length;
5
6        // Initialize the array to store answers for the queries
7        int[] answers = new int[m];
8
9        // Loop through every query
10        for (int i = 0; i < m; ++i) {
11            // Extract the start and end points (a and b) from the current query
12            int start = queries[i][0], end = queries[i][1];
13          
14            // Initialize the cycle length as 1 for the current query
15            int cycleLength = 1;
16          
17            // While the start point is not equal to the end point
18            while (start != end) {
19                // If start is greater than end, right shift start (equivalent to dividing by 2)
20                if (start > end) {
21                    start >>= 1;
22                } else {
23                    // If start is not greater than end, right shift end
24                    end >>= 1;
25                }
26                // Increase the cycle length counter since we've made a move
27                ++cycleLength;
28            }
29
30            // Store the computed cycle length in the answers array
31            answers[i] = cycleLength;
32        }
33
34        // Return the array containing answers for all queries
35        return answers;
36    }
37}
38
1#include <vector>
2
3class Solution {
4public:
5    // Function to find the cycle lengths in a binary tree for given queries
6    // @param n : an integer representing the number of nodes in a full binary tree
7    // @param queries : a vector of queries where each query is a vector of two integers
8    // @return : a vector of integers representing the cycle lengths for each query
9    vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
10        // Initialize a vector to store the answers for each query
11        vector<int> answers;
12      
13        // Iterate over each query in the list of queries
14        for (auto& query : queries) {
15            // Extract the two nodes being queried from the current query
16            int nodeA = query[0], nodeB = query[1];
17          
18            // Initialize a variable to keep track of the number of steps in the cycle
19            int steps = 1; // Starting from 1 because the first node is also counted as a step
20          
21            // Keep adjusting the nodes until they are equal, which means they have met at their common ancestor
22            while (nodeA != nodeB) {
23                // If nodeA is greater than nodeB, move it one level up towards the root
24                if (nodeA > nodeB) {
25                    nodeA >>= 1; // Equivalent to nodeA = nodeA / 2;
26                } else {
27                    // Otherwise, move nodeB one level up towards the root
28                    nodeB >>= 1; // Equivalent to nodeB = nodeB / 2;
29                }
30              
31                // Increase the step count with each move
32                ++steps;
33            }
34          
35            // Once the common ancestor is reached, add the step count to the answers list
36            answers.emplace_back(steps);
37        }
38      
39        // Return the answers to the queries
40        return answers;
41    }
42};
43
1function cycleLengthQueries(numberOfNodes: number, queries: number[][]): number[] {
2    // Initialize an array to store the answers for each query
3    let answers: number[] = [];
4  
5    // Iterate over each query in the list of queries
6    for (let query of queries) {
7        // Extract the two nodes being queried from the current query
8        let nodeA: number = query[0];
9        let nodeB: number = query[1];
10
11        // Initialize a variable to keep track of the number of steps in the cycle
12        // Starting from 1 because the first node is also counted as a step
13        let steps: number = 1;
14      
15        // Keep adjusting the nodes until they are equal, which means they have met at their common ancestor
16        while (nodeA !== nodeB) {
17            // If nodeA is greater than nodeB, move it one level up towards the root
18            if (nodeA > nodeB) {
19                nodeA >>= 1; // This is a bitwise operation equivalent to dividing nodeA by 2 and flooring the result
20            } else {
21                // Otherwise, move nodeB one level up towards the root
22                nodeB >>= 1; // This is a bitwise operation equivalent to dividing nodeB by 2 and flooring the result
23            }
24          
25            // Increase the step count with each move
26            steps++;
27        }
28      
29        // Once the common ancestor is reached, add the step count to the answers array
30        answers.push(steps);
31    }
32  
33    // Return the answers to the queries
34    return answers;
35}
36
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

Time Complexity

The given code executes a for loop over the queries list, which contains q pairs (a, b), where q is the number of queries. Within this loop, there's a while loop that runs until the values of a and b are the same. In the worst case, this while loop runs for the height of the binary tree which represents the number of divisions by 2 that can be done from the max value of a or b down to 1. Given that a and b are less than or equal to n, the height of such a tree would be O(log(n)).

Thus, for q queries, the while loop executes at most O(log(n)) for each pair. Therefore, the time complexity for the entire function is O(q * log(n)) where q is the length of the queries list and n is the maximum value of a or b.

Space Complexity

The space complexity of the code is relatively simpler to assess. It uses an array ans to store the results for each query. The size of this array is directly proportional to the number of queries q which is the length of the input queries list. No additional significant space is required; thus, the space complexity is O(q).

No complex data structures or recursive calls that would require additional space are used in this solution.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫