3.3.8. Questions

3.3.8.1. Step-By-Step Directions From a Binary Tree Node to Another

You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.
Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:
'L' means to go from a node to its left child node.
'R' means to go from a node to its right child node.
'U' means to go from a node to its parent node.
Return the step-by-step directions of the shortest path from node s to node t.

Example:
                    +---+
                    | 0 |
                    +---+
                   /     \
              +---+       +---+
              | 1 |       | 2 |
              +---+       +---+
             /     \           \
        +---+      +---+       +---+
        | 3 |      | 4 |       | 5 |
        +---+      +---+       +---+

From 3 to 2, the shortest path is 3->1->0->2, so the direction string is UUR.
From 4 to 5, the shortest path is 4->1->0->2->5, so the direction string is UURR.

It’s no hard to see that the shortest path is from the start node to the lowest common ancestor (LCA) of (start, end), then to the end node. The key is to find the LCA while finding paths from root to two nodes.

We can use recursion to find/build a path from root to a target node. The common prefix of these two paths is the path from root to the LCA that we need to remove from the shortest path: e.g. root to start “LLRLR”, root to dest “LLLR”.

common prefix is “LL”, after removing, it becomes: LCA to start “RLR”,LCA to dest “LR”. Final path becomes “UUU” + “LR” = “UUULR”

The final step is to replace the L/R with U for the start path since we are moving up and then concatenate with the target path.

Time complexity: O(n) Space complexity: O(n)

struct Solution {
  string getDirections(TreeNode* root, int start, int dst) {
    string s, d;
    get_path(root, start, s), get_path(root, dst, d);
    while (!s.empty() and !d.empty() and s.back() == d.back())
      s.pop_back(), d.pop_back();
    reverse(begin(d), end(d));
    return string(s.size(), 'U') + d;
  }
  bool get_path(TreeNode* root, int t, string& path) {
    if (!root) return false;
    if (root->val == t) return true;
    if (get_path(root->left, t, path)) {
      path.push_back('L');
      return true;
    } else if (get_path(root->right, t, path)) {
      path.push_back('R');
      return true;
    }
    return false;
  }
};

https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/

3.3.8.1.1. Second Smallest Number 🥷

Given an array of integers, find the minimum element and the element just greater than that in less than 2N comparisons. The given array is not necessarily sorted. Extra space is allowed.

Examples:

Input: {3, 6, 100, 9, 10, 12, 7, -1, 10}

Output: Minimum: -1, Second minimum: 3

3.3.8.1.2. Buddy Bitmap 🥷

Buddy Bitmap is a fully populated binary tree that contains 0 or 1 at each node.
Invariant: a non-leaf node contains 1 if and only if both of its child nodes contain 1.

Here's an example of a buddy bitmap:

Level 0:            0
               ___/   \___
Level 1:      0           0
            /   \       /   \
Level 2:   1     0     0     1
          / \   / \   / \   / \
Level 3: 1   1 0   0 0   0 1   1

Offset:  0   1 2   3 4   5 6   7      (at level 3)

Each node is identified by its level and index within the level.

The operations that are provided to you in a library are:
1) NUM_LEVELS                       # constant that has the number levels (e.g. 4 in the example)
2) ClearBit(int level, int offset)  # assigns the value of the bit by the `level` and `offset` to 0

Please implement function:

  ClearBits(int offset, int range)  # Clears `a range of` bits starting at `offset` at the last level

The tricky part is the indexing scheme. From this question, we can see parent_index is equal to child_index/2. Also the buddy bitmap uses bit-wise and as the merging scheme, so the parent is 0 if any of its children is 0.

void clearBits(int offset, int range) {
  int cl = NUM_LEVELS-1;
  int first = offset, last=offset+range-1;
  while(cl>=0){
    for(int i=first; i<=last; i++)
      ClearBit(cl, i);
    first /= 2, last /= 2;
    cl--;
  }
}

Follow-up Questions:

Given:
3) SetBit(level, offset)        # sets the bit at `level` and `offset`
4) GetBit(level, offset) -> 0/1 # returns the value at `level` and `offset`

Pleas implement function:

  SetBits(offset, range) # Sets `range` bits starting at `offset` at the last level

Setting bit is trickier than clearing bit. To set the parent, we need to make sure the both children are set too.

void SetBits(int offset, int range) {
  int cl = NUM_LEVELS-1;
  int first = offset, last=offset+range-1;
  while(cl>=0){
    for(int i=first; i<=last; i++){
      if (cl==NUM_LEVELS-1)
        SetBit(cl, i);
      else{
        if (i==first){
          if (GetBit(cl+1, 2*i)){
            SetBit(cl, i);
          }
        }
        if(i==last){
          if (GetBit(cl+1, 2*i+1)){
            SetBit(cl, i);
          }
        }
        if (i!=first and i!=last){
          SetBit(cl, i);
        }
      }
    }
    first /= 2, last /= 2;
    cl--;
  }
}

We can consolidate all the conditions into one clause and get the simpler form:

void SetBits(int offset, int range) {
  int cl = NUM_LEVELS-1;
  int first = offset, last=offset+range-1;
  while(cl>=0){
    for(int i=first; i<=last; i++){
      if (cl==NUM_LEVELS-1 or 
            (i==first and GetBit(cl+1, 2*i)) or
            (i==last and GetBit(cl+1, 2*i+1)) or
            (i!=first and i!=last))
        SetBit(cl, i);
    }
    first /= 2, last /= 2;
    cl--;
  }
}

This question is related to Segment Tree(Section 3.3.3).

3.3.8.1.3. Design Segment Tree

Design a data structure to represent a specialized segment tree where each node can either be a leaf node or an internal node. An internal node possesses two children—specifically, a left child and a right child—and stores the total length of all descendant nodes. A leaf node, in contrast, holds a specific value alongside its length. Consider the structure illustrated below as an example:

     InternalNode, 26
     /              \
    /                \
   /                  \
Leaf(5, "ABCDE")    InternalNode, 21
                      /           \
                     /             \
                    /               \
                   /                 \
        Leaf(10, "FGHIJKLMNO")   Leaf(11, "PQRSTUVWXYZ")

Question 1 - Data Structure Design:

Propose a data structure that effectively models the described segment tree. Ensure your design can accommodate both leaf nodes, which contain a string value and a length, and internal nodes, which maintain the combined length of their child nodes.

Question 2 - Character Retrieval Function:

Develop a function that, given a tree (as per the data structure you’ve designed) and an index, returns the character located at that specific index within the tree. The index refers to the position in the concatenated string formed by traversing all leaf nodes in order.

This can be done by segment tree or cord tree.

3.3.8.1.4. Manipulate Long String

Design a tree-based data structure to efficiently manipulate a very long string.

class LongString {
public:
  LongString(string s) {...}

  // Returns the character at index 'i', if not available, return null or ''
  char index(int i) {...}

  // string length
  char size() {...}

  /* Remove the specified character substring. The substring begins at the specified 'start' and extends to the character  at index 'end - 1' or to the end of the sequence, if no such character exists. If 'start' is equal to 'end', no changes are made.
  @param   start  The beginning index, inclusive.
  @param   end    The ending index, exclusive.
  @return  false if 'start' is negative,  greater than length, or greater than 'end'. */
  bool remove(int start, int end) {...}
}

Hint:

Segment tree
Cord tree

In computer programming, a rope, or cord, is a data structure composed of smaller strings that is used to efficiently store and manipulate a very long string. For example, a text editing program may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently. A rope is a left-ish binary tree (that is, each node can have maximum of 2 children) where each leaf (end node) holds a string and a length (also known as a “weight”), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree.

For string “ABCDEFGHIJKLMNOPQRSTUVWXYZ”, you can use the following cord tree to store it:

     InternalNode, 5
     /              \
    /                \
   /                  \
Leaf(5, ABCDE)      InternalNode, 10
                      /           \
                     /             \
                    /               \
                   /                 \
        Leaf(10, FGHIJKLMNO)     Leaf(11, PQRSTUVWXYZ)

Solution:

Please refer to Cord Tree(Section 3.3.6) for the details.

#include <gtest/gtest.h>
#include <sein.hpp>

namespace ns_adv_tree_cord {
struct node {
  node *left = nullptr, *right = nullptr;
  int len = 0;
  string s = "";
  bool is_leaf() { return !s.empty(); }
  node(node *l = 0, node *r = 0, int sz = 0, string s_ = "") : left(l), right(r), len(sz), s(s_) {}
};
int tree_size(node *c) { // O(LogN)
  int r = 0;
  while (c) r += c->len, c = c->right;
  return r;
}
node *merge(node *x, node *y) {
  return new node(x, y, tree_size(x));
}
pair<node *, node *> split(node *n, int i) {  // 💣
  if (n->is_leaf()) {
    node *l = new node(0, 0, i, n->s.substr(0, i));
    node *r = new node(0, 0, n->len - i, n->s.substr(i));
    return {l, r};
  }
  if (i < n->len) {
    auto[x, y] = split(n->left, i);
    return {x, merge(y, n->right)};
  }
  if (i == n->len) return {n->left, n->right};
  auto[x, y] = split(n->right, i - n->len);
  return {merge(n->left, x), y};
}

struct LongString {
  node *root;
  const int LEAF_MAX_LEN = 8;
  explicit LongString(const string &s) {
    root = _construct(s, 0, s.size() - 1);
  }
  node *_construct(const string &s, int h, int t) {  // 💣
    int l = t - h + 1;
    node *n = new node();
    if (l > LEAF_MAX_LEN) {
      n->len = l / 2;
      n->left = _construct(s, h, h + l / 2 - 1);
      n->right = _construct(s, h + l / 2, t);
    } else {
      n->len = l;
      n->s = s.substr(h, l);
    }
    return n;
  }
  char index(int i) { return _index(root, i);}
  char _index(node *n, int i) {
    if (n->is_leaf()) return n->s.at(i);
    if (i < n->len) return _index(n->left, i);
    return _index(n->right, i - n->len);
  }
  bool remove(int start, int end) {  // 💣
    if (start < 0 or start > root->len or start > end) return false;
    auto x = split(root, start);
    auto y = split(root, end);
    root = merge(x.first, y.second);
    return true;
  }
  void push_back(const LongString &ls) { root = merge(root, ls.root); }
  void push_front(const LongString &ls) { root = merge(ls.root, root); }
  string get_string() {return _get_string(root);}
  string _get_string(node *r) {
    if (r->is_leaf()) return r->s;
    return _get_string(r->left) + _get_string(r->right);
  }
  int size() {return tree_size(this->root);}
};
}
using namespace ns_adv_tree_cord;
TEST(_adv_tree_cord_tree, a) {
  LongString ls("012345678901234567890123456789");
  EXPECT_EQ(ls.index(12), '2');
  EXPECT_EQ(ls.size(), 30);
  EXPECT_EQ(ls.get_string(), "012345678901234567890123456789");
  ls.remove(8, 28);
  EXPECT_EQ(ls.get_string(), "0123456789");
  EXPECT_EQ(ls.size(), 10);
}