# DSA Tree (Hand-Written Part)
###### tags: ntu
</br>

> ## Q1. So many trees (Tree Traversal)

### Q1-1. (Easy)
Construct all possible binary trees from the given traversal.

1.
- Pre-order traversal: $[E, A, B, G, C, D, H, I]$
- In-order traversal: $[B, G, A, C, E, D, I, H]$
2.
- Pre-order traversal: $[A, B, E, C, D]$
- Post-order traversal: $[E, D, C, B, A]$

### Q1-2. (Easy~Medium)

> ###### I don't know which one is better

1. Discuss why a unique binary tree can be constructed by giving in-order and pre/post-order traversal sequence, but not with pre-order and post-order traversal sequence. Please elaborate both cases with concise explanation.

2. Bob claimed that: "*Given an in-order and a pre-order or post-order traversal sequence, a unique binary tree can be constructed.*" Is Bob correct? If so, briefly explain your algorithm to constuct the unique binary tree; if not, provide a counter-example.

### Q1-3. (Medium~Hard)
Given a pre-order and a post-order traversal sequence of a binary tree with $N$ nodes, design an alogrithm to calculate the number of all possible binary trees that satisifies both sequence. Your algorithm must run in $O(N^2)$ with $O(1)$ auxiliary space. Please describe your algorithm using pseudocode consisting of no more than 30 lines and provide a brief explanation of its correctness and complexity. You can assume that the given traversal sequences are valid (i.e. can at least construct one binary tree) and have no duplicated key.

</br>

> ## Q2. Is this tree that tree (Mirrored Tree)

Two trees $T_{1}$ and $T_{2}$ are regarded as "***mirrored***" if
1. The root values of both trees are the same.
2. The left subtree of $T_{1}$ is mirrored to the right subtree of $T_{2}$
3. The right subtree of $T_{1}$ is mirrored to the left subtree of $T_{2}$

Ze is asked if he can modify a node in $T_{1}$ while also maintaining $T_{2}$ as a mirrored tree of $T_{1}$. Can you help him?

> For the following question, please describe your algorithm using pseudocode consisting of no more than 30 lines and provide a brief explanation of its correctness and complexity.

### Q2-1. (Easy~Medium)
Now consider two mirrored complete binary trees $BT_{1}$ and $BT_{2}$ with $N$ nodes each, where each node is labeled according to its position in the level-order traversal, starting from $0$ to $N-1$. Given $M$ operations $op$, where $op_{i}$ consists of two integers $idx_{i}, value_{i}$ ($1\leq i \leq M,\ 0\leq idx_{i} \leq N-1$). Design an algorithm that changes the value of the node with label $idx_{i}$ in $BT_{1}$ and its corresponding node in $BT_{2}$ to $value_{i}$. Your algorithm should run in $O(MlogN)$ in total with $O(logN)$ auxiliary space.

For this question, please follow the definition of a node below:

struct Node {
    int value;
    Node* left;    // Left Subtree
    Node* right;   // Right Subtree
}

### Q2-2. (Medium)
Now consider two mirrored complete ***k-ary*** trees $T_{1}$ and $T_{2}$ with $N$ nodes each, where each node is labeled according to its position in the level-order traversal, starting from $0$ to $N-1$. With the same $M$ operations $op$, design an algorithm that changes the value of the node with label $idx_{i}$ in $BT_{1}$ and its corresponding node in $BT_{2}$ to $value_{i}$. Your algorithm should run in $O(MlogN)$ in total with $O(logN)$ auxiliary space.

For this question, please follow the definition of a node below:

struct Node {
    int value;
    Node* children[k] = {NULL, NULL, ... , NULL};    // Subtree 1 (left-most) to Subtree k (right-most)
}

## - Solution

> 1. Arrays are 0-based
> 2. for i=a to b $\iff$ for(int i=a; i<=b; i++)
### Q2-1.

### Q2-2.

### Q2-3.
略

### Q2-4.

Function solve(N, preorder[N], postorder[N]):
    ans = 1
    for i=0 to N-2:
        for j=1 to N-1:
            if(preorder[i]==postorder[j] and preorder[i+1]==postorder[j-1]):
                ans*=2;
    return ans;

### Q2-5.

// 0: left subtree, 1: right subtree
getRouteToTheNodeWithIndex(idx):
    Stack s
    while(idx > 0):
        s.push((idx-1)%2)
        idx = (idx-1) // 2
    return s

solve(BT1, BT2, N, M, op[M]):
    for i = 1 to M:
        Stack route = getRouteToTheNodeWithIndex(op[i].idx)
        root1 = BT1, root2 = BT2, cur_idx = 0
        while(cur_idx != op[i].idx):
            dir = route.top(), route.pop()
            if(dir == 0)
                root1 = root1.left, root2 = root2.right, cur_idx = 2*cur_idx + 1
            else if(dir == 1)
                root1 = root1.right, root2 = root2.left, cur_idx = 2*cur_idx + 2
        root1.value = op[i].value
        root2.value = op[i].value    

### Q2-6.

#### Intuition
- Q2-5是透過backtracking來找到從node走到target的path, 因此需要$O(logn)$-extra-space
- $O(1)$-extra-space 需要邊走邊計算
- 給定一個target node with label $x$, 透過計算x在當前node(從root出發後走到的node)的哪一個subtree上來決定現在要往哪一個child走

#### Algorithm
- Step 1: Find the level $l$ for target node x (`root` is at level $0$)
- Solve
$$k^0+k^1+\cdots+k^l \ge x \ge k^0+k^1+\cdots+k^{l-1}$$
- Equilvalent to solve
$$ \min_{l}{\frac{k^{l+1}-k^{0}}{k-1} \ge x}$$
- Hence
$$l = ceiling(log_k{((k-1)x+1)}-1)$$

- Step2: Find the label $m$ of the first (left-most) node in the current level $l$
>($l$ from Step 1)
- Solve
$$
\begin{align}
m&= (k^0+k^1+\cdots+k^{l-1}) + 1\\
&= \frac{k^{l}-k^{0}}{k-1} + 1
\end{align}
$$

- Step3: Find the offset of $x$, denoted as $x'$ in its level ($l$)
> Offset of $m$ will be $0$, then count from left to right
> e.g. $10$ in a $4$-ary tree will have offset $4$
- Solve
$$
x' = x-m
$$

- Step4: Calculate $p$, denoting the number of leaves for each subtree of current position node.
- Solve
- Suppose we are at node $y$ at level $a$, then for each subtree with root being one of the children of $y$ has
$$
p = k^{l-a-1}
$$

- Step5: Calculate the direction $d$ of which subtree $x$ is on ($i.e.$ which child should we move to) at the current position
> $d=0$ : left-most child
> $d=k-1$: right-most child
> $//:=$ integer division
- Solve
$$
d = x'\ //\ p
$$
- Then move to the current position to the child by `cur = cur.children[d]`

- Step6: Update the offset $x'$
> Since we now have smaller subtrees
> We subtract the number of nodes for all subtrees from the left of the current subtree
- Solve
$$
\begin{align}
x' &= x' - (x'\ //\ p)*k^{l-a-1}\\
&= x' - d*p
\end{align}
$$

- Step7:
- If $x' == 0$, we have found the target node $x$.
- else, go to Step4

solve(T1, T2, k, N, M, op[]):
    for i = 1 ~ M
        l = -1, sum = 0, k_pow_l = 1, x = op[i].idx
        while x > sum
            sum += k_pow_l
            k_pow_l *= k
            l++
        k_pow_l /= k        # k^l where l = ceiling(log_k{((k-1)x+1)}-1)
        m = (k_pow_l - 1) / (k - 1) + 1
        x` = x - m 
        root_1 = T1
        root_2 = T2
        while x` > 0
            k_pow_l /= k    # Equivalent to p = k^{l-a-1}
            d = x` // k_pow_l
            root_1 = root.children[d]
            root_2 = root.children[k-d-1]
            x` = x` % k_pow_l
        root_1.val = root_2.val = op[i].val