Trees Flashcards
Check if a tree is a Binary Search Tree
For any node u check that:
* keys in left subtree of u are smaller than or equal to u.key
* keys in right subtree of u are larger than u.key
Longest k-good segments (subarray)
Given an integer array and an integer K, return the number of good subarrays. A good array is an array where the number of different integers in that array is exactly K.
Solution with two pointers technique and dynamic sliding window.
Two pointers, left and right, both starting at position 0. Keep a counter to count the number of distinct elements in the window and a map value -> # occurrences.
Until the right pointer reaches the end do:
* if the counter is <= K, move right pointer. Increment the #occurrences of the new entry in the window. If it is 1 then it is the first time that value is in the window, then increment the counter also
* else the counter is > K, move left pointer. Decrement the #occurrences of the value which is not in the window anymore. If it is 0 then that value is not in the window in other positions, then decrement the counter also
* during the loop keep track of largest subarray
Theta(n) whp: no more than 2n iterations which means theta(n) operations on the map
Longest k-good segments (subarray)
Implement a theta(n) worst case solution if values are in [1, …, O(n)].
Given an integer array and an integer K, return the number of good subarrays. A good array is an array where the number of different integers in that array is exactly K.
Solution with two pointers technique and dynamic sliding window.
Two pointers, left and right, both starting at position 0. Keep a counter to count the number of distinct elements in the window and an array to store #occurrences (direct access table).
Until the right pointer reaches the end do:
* if the counter is <= K, move right pointer. Increment the #occurrences of the new entry in the window. If it is 1 then it is the first time that value is in the window, then increment the counter also
* else the counter is > K, move left pointer. Decrement the #occurrences of the value which is not in the window anymore. If it is 0 then that value is not in the window in other positions, then decrement the counter also
* during the loop keep track of largest subarray
Euler Tour
It is a mix of pre and post order visits
if (node != NULL) do something with node.key EulerTour(node.left) EulerTour(node.right) do something with node.key
Maximum Path Sum
Given a tree with n nodes, each node u has a weight w(u). Find the maximum sum of a path from one leaf to another leaf.
Let’s say U is the LCA (Lowest Common Anchestor) of the leaves L1 and L2. The optimal path can be decomposed into two subpaths: L1 -> U and L2 -> U.
Run a post order visit in theta(n) time, for each node U:
* compute max path sum from U to a leaf in left subtree (msl) and in right subtree (msr)
* the best maximum path sum at the node U is equal to w(u) + msl + msr (w(u) + max sum left + max sum right)
Path Sum
Design a data structure to efficiently answer the query PathSum(u, v), which returns the sum of weights on path from u to v. Give a O(1) time solution.
TODO how to solve it if the weights change
If w = LCA(u, v) then PathSum(u, v) = PathSum(w, u) + PathSum(w, v) - w(w).
We remove w(w) because it is counted twice.
Let’s assume we can compute LCA(u, v) in O(1) time. We can focus on the case PathSum(w, v) in which node w is anchestor of node v. PathSum(w, v) = PathSum(root, v) - PathSum(root, w) + w(w).
We add w(w) because we are cancelling that weight in the subtraction.
To solve the problem the goal is to compute PathSum(root, any node)
Precompute and store all of them with a pre order visit.