---
# System prepended metadata

title: Tree★★★
tags: [Data Structure]

---

# **TOC**
[TOC]
# <font color="#365c0c">**Tree Introduction**★</font>
> <font color="#000000">Link List is an ++one-dimensional++ structure.</font>
A、B、C、D are nodes can represent data, state, etc。
the link between nodes call edges, may be unidirected or directed.

![](https://i.imgur.com/prYe9Ty.png)

> <font color="#000000">Tree and Graph is an ++multidimensional++ structure.</font>

<font color="#000000">Set-relationship</font>
<span style="display:block;text-align:center;">![](https://i.imgur.com/Lsw7ulp.png)</span>
Tree is a preferred option when we confront to ++hierarchical problems++,
that means we have ++sequence(order)++ in this structure.

Example: Premutation (R is the *root* of *Tree*)
![](https://i.imgur.com/GD6DlX3.png)

In these picture, we choose the first alphabet A, B, C from root, then choose the second one, and so on.

<!--![](https://i.imgur.com/W2yMEG5.png)-->
* <font color="#3770b4">**Definition**</font>

    A *Tree* is a finite set of *>0* nodes such that
    1. There is a specially designated node called `root` 
    2. The remaining nodes can be partitioned into *n≥0* ++disjointed sets++ *T~1~...T~n~* are called the `subtree` of the `root`. (means there is ++no cycle in tree++)
* <font color="#3770b4">**Discription**</font>
	
	***Node:***
    * ***degree:*** The number of subtrees of a node.
        *   *degree(T)=max{node's degree}*
        * *degree(A)=3*
        * *degree(B)=2*
     * ***height/depth:***
         *   *height(T)=max{node's level}* 
         *   *height(F)=2*
         :::warning
		 height = depth
		 :::
    * ***root:*** The most upper layer node which parent is NULL.
        * *root(T)=A*
    *  ***leaf:*** The node doesn't have child/subtree.
        *  *leaf(T)=G、H、J、K、L、M、N*
    *  ***external node：*** The node doesn't have child.
        *  ++external_node=leaf++
    *  ***internal node：*** The node has ++a least one child++.
        *  *internal_node(T)=A、B、C、D、E、F、I*
    <span style="display:block;text-align:center;">![](https://i.imgur.com/lctoEtK.png)</span>
    
    ***Tree:***
    *    ***parent->child:***
         *    *A(parent)->C(child)*
    *    ***siblings:*** The nodes have same parent
         *    *sibling(B)=C、D*
    *    ***ancestor:*** The nodes travel through child->parent direction of a node.
         *    *ancestor(F)=C、A*
    *    ***descendant:*** The nodes travel through parent->child direction of a node.
         *    *descendant(F)=L、M*
    *    ***path:*** The nodes in ancestor and descendent relationship.
         *    *A-B-E-K*
    *    ***level:*** 
         *    *level(root)=1*
         *    *level(child)=level(parent)+1*
              *    *level(I)=3*
    ***Forest***
    * A set of n≥0 Trees
    ![](https://hackmd.io/_uploads/HJ9kB4Blp.png)
# <font color="#365c0c">**Tree's Representaion**</font>
## **Link List**
* <font color="#3770b4">**Definition**</font>
    * node_num(T)=n
    * degree(T)=k
    ![](https://hackmd.io/_uploads/SJHxf4Sla.png)
* **Analysis**
    * Pros
        * None
    * Cons
        * Waste link list memory
            * Total: *n-k*
            * Used: *n-1*
            * Waste Rate: *k-1/k* (k=2 B.T)
## **Sibling child**
* <font color="#3770b4">**Definition**</font>
    * Parent->left_most_child
    * child->right_sibling
    ![](https://hackmd.io/_uploads/HkUH7VrlT.png)
## **Bracket**
* <font color="#3770b4">**Definition**</font>
    * Parent(C~1~ ... C~n~)
        * A(B(EF)C(GD(HIJ))
        ![](https://hackmd.io/_uploads/By9LrVrgT.png)
## **Binary Tree(B.T)**
* <font color="#3770b4">**Definition**</font>
    * A *B.T* is a finite set of *≥0* nodes, if > 0 then
    * `root->left_subtree`
    * `root->right_subtree`
    * `left_subtree` and `right_subtree` ∈ B.T
* **Tree v.s. B.T**
    | Tree | B.T  |
    | ---- | ---- |
    | n>0     | n≥0     |
    | 0≤degree(T)     | 0≤degree(T)≤2     |
    | unordered | ordered(left,right) |
    
    ![](https://hackmd.io/_uploads/Bkl7_v4Bxa.png)

# <font color="#365c0c">**Binary Tree★★**</font>
* <font color="#3770b4">**Definition**</font>
    * [above](##Binary-Tree(B.T))
* <font color="#3770b4">**Properties**</font>
	\begin{aligned}
	&height(T)=h \\
	&\text{At most: }2h-1\text{ nodes}\\ 
	&num(degree==0)=n_0 (leaf) \\
	&num(degree(nodes)==2)=n_2 \\
	&n_0= n_2+1 &&\text{(★★★)} \\
	&n = n_0+n_1+n_2 \\
	&n = B+1 = 1*n_1+2*n_2+1 &&B\text{ = totoal num of edge}\\
	&n = n_0+n_1+n_2 = 1*n_1+2*n_2+1 \\
	\end{aligned}
	![](https://hackmd.io/_uploads/r13heBSxa.png)
	![](https://hackmd.io/_uploads/B1we4rrl6.png)
	![](https://hackmd.io/_uploads/HyFpVrSea.png)
* <font color="#3770b4">**Type of B.T**</font>
    * **Skewed B.T**
        * left-skewed B.T
        * right-skewed B.T
        
        <img src="https://hackmd.io/_uploads/Syf2UrHga.png" width="360" height="180">
    * **Full B.T**
        * *num(nodes) = 2^h^-1*
    * **Complete B.T**
        * *height(T) = h, num(nodes) = n*
        * *2^h-1^-1<n≤2^h^-1*
        * ==*h = ⌈log~2~(n+1)⌉*==
        * order of *Tree* is from
            * top to bottom
            * left to right
        
        ![](https://hackmd.io/_uploads/ByaguSHxT.png)
        * ==*n~1~ to n~n~, n~i~*==
            * leftchild: *2i*
                * if *2i>n, n~i~->left_child=null*
            * rightchild: *2i+1*
                * if *2i+1>n, n~i~->right_child=null*
            * parent: *[i/2]*, expect *root*
        
        ![](https://hackmd.io/_uploads/HJ2-VUBea.png)
        ![](https://hackmd.io/_uploads/SJFmVLHlp.png)
        ![](https://hackmd.io/_uploads/rypUV8HeT.png)        
        
        *n~i~'->left_node=2i*
        
        *n~500~'->left_node=1000*
        
        *n~500~\~n~1000~ are leaves*
        
        ![](https://hackmd.io/_uploads/r1m6LwBxp.png)
    * **Strict B.T**
        * *degree(non-leaf nodes)=2*
        * *num(degree(n)==1)=0*
        <br>
		![](https://hackmd.io/_uploads/HyktYDrxa.png)
		![](https://hackmd.io/_uploads/BJAgqDHxa.png)
# <font color="#365c0c">**B.T's Representaion**</font>
## **Array**
* <font color="#3770b4">**Definition**</font>
    * *height(T)=h*
    * arr[1...2^h^-1]={}
    
    ![](https://hackmd.io/_uploads/Hy6AeOHep.png)
    * pros
        * easy to get the nodes by index
        * suit to Full/Complete B.T
    * cons
        * diffcult to add/delete/move nodes
        * not suit to Skewed B.T
            * Waste memo: 2^h^-1-h 
## **Link List★**
* <font color="#3770b4">**Definition**</font>
    ```cpp
    typedef struct TreeNode
    {
        int data;
        TreeNode *leftChild;
        TreeNode *rightChild;
        //TreeNode *parent;
    }TreeNode;
    ```
    ![](https://hackmd.io/_uploads/BkrfzdSg6.png)
    * pros
        * easy to add/delete/move nodes
        * suit to Skewed B.T
    * cons
        * not ease to save parent node, but still acceptable
        * link will waste *50%* memory space
            * *num(nodes)=n, 2n links*
            * *n-1 links != null*
            * *n+1 links == null*
# <font color="#365c0c">**Traversal★★★**</font>
There is *3!=6* kinds of Traversal

But we restrict that meet left befor right
* **DFS**
    * **Pre-order:** parent->left->right
    * **In-order:** left->parent->right
    * **Post-order:** left->right->parent
* **BFS** 
    * Level-order:
        * top to bottom
        * left to right

![](https://i.imgur.com/t9mmRRL.png)

<span style="display:block;text-align:center;">![](https://i.imgur.com/iAOlGN9.png)</span>
:::spoiler **Code**     
```cpp
//DFS
//preorder
void preorder(TreeNode *root)
{
    output(root);
    preorder(root->leftChild);
    preorder(root->rightChild);
}
//Inorder
void Inorder(TreeNode *root)
{
    Inorder(root->leftChild);
    output(root);
    Inorder(root->rightChild);
}
//postorder
void postorder(TreeNode *root)
{
    postorder(root->leftChild);
    postorder(root->rightChild);
    output(root);
}
//level order(BFS)
void levelorder(TreeNode *root)
{
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        TreeNode *curNode = q.front();
        q.pop();
        output(curNode);
        if(curNode->left!=NULL)
            q.push(curNode->leftChild);
        if(curNode->right!=NULL)
            q.push(curNode->rightChild);
    }
}
```
:::
* **Complexity**
    * DFS: *O(n)*
    * BFS: *O(n)*
## **Reconstruction B.T★★★**
If we only have one order, we can't reconstruct a new binary tree, because there various prosiblilities.

<span style="display:block;text-align:center;">![](https://i.imgur.com/g2o4BhM.png)</span>

So once have two order, we can find the unique binary tree?

No!only when we have two kinds of order conbination.
1. Preorder-Inorder →
    * PLR: the first node is `root`
    * LPR: get the `left_subtree` and `right_subtree` by `root`
2. Postorder-Inorder ←
    * LRP: the last node is `root`
    * LPR: get the `left_subtree` and `right_subtree` by `root`
3. ~~Preorder-Postorder~~
    * Preorder-Postorder can't identify the position of root
4. Level-order-Inorder
:::warning
Must have **inorder** to part left and right
:::
<span style="display:block;text-align:center;">![](https://i.imgur.com/Corax4U.png)</span>

![](https://hackmd.io/_uploads/SyYmcOHe6.png)
![](https://hackmd.io/_uploads/H1s7ScHxT.png)
Preorder-Postorder: Try and Error by person
![](https://hackmd.io/_uploads/SJ84g5Bxa.png)
++Pre-order:a b c++

++Post-order: c b a++

There are ++4++ conditions fullfill the order
![](https://hackmd.io/_uploads/HJhq-5SgT.png)
![](https://hackmd.io/_uploads/HJzqz5rlp.png)
![](https://hackmd.io/_uploads/r1ZwQqrg6.png)
:::info
If a **Full/Complete** tree are given only an order.
We can still restruct it
:::
![](https://hackmd.io/_uploads/r1FsI9rgp.png)

:::spoiler **Code**
```cpp
//c++
typedef struct TreeNode
{
    int val;
    TreeNode *leftChild;
    TreeNode *rightChild;
}TreeNode;

TreeNode *newTreeNode(int val)
{
    TreeNode *newTreeNode = (TreeNode*)malloc*(sizeof(TreeNode));
    newTreeNode->val = val;
    newTreeNode->leftChild = NULL;
    newTreeNode->rightChild =NULL;
}
//reconstruct tree by comparing index of inorder
void buildTree(TreeNode *curNode, vector<int> inorderIDX, int insert_val)
{
    while(true)
    {
        if(inorderIDX[intsert_val] < inordorIDX[curNode->val])
        {
            if(curNode->leftChild == NULL)
            {
                curNode->leftChild = newNode(insert_val);
                return;
            }
            else
                curNode = curNode->left;
        }
        if(inorderIDX[intsert_val] > inordorIDX[curNode->val])
        {
            if(curNode->rightChild == NULL)
            {
                curNode->rightChild = newNode(insert_val);
                return;
            }
            else
                curNode = curNode->right;
        }
    }
}
int main()
{
    string order_type;
    cin >> order_type;
    int num_nodes;
    cin >> num_nodes;
    vector<int> preorder(-1, num_nodes);
    vector<int> postorder(-1, num_nodes);
    vector<int> inorderIDX(-1, num_nodes);
    if(order_type == "preorder-inorder")
    {
        int tmpIDX = -1;
        for(int i=0; i<num_nodes; i++)
            cin >> preoroder[i];
        for(int i=0; i<num_nodes; i++)
        {
            cin >> tmpIDX;
            inorderIDX[tmpIDX] = i;
        }
        //root is first element in preorder
        TreeNode *root = newNode(preorder[0]);
        for(int i=1; i<num_nodes; i++)
            buildTree(root, inorderIDX, preorder[i]);
    }
    else if(order_type == "postorder-inorder")
    {
        int tmpIDX = -1;
        for(int i=0; i<num_nodes; i++)
            cin >> postoroder[i];
        for(int i=0; i<num_nodes; i++)
        {
            cin >> tmpIDX;
            inorderIDX[tmpIDX] = i;
        }
        //root is last element in preorder
        TreeNode *root = newNode(postorder[num_nodes]);
        for(int i=num_nodes; i>0; i--)
            buildTree(root, inorderIDX, postorder[i]);
    }
    return 0;
}
```
:::
## **B.T operation**
* **copy a B.T**
    ```cpp
    //preorder
    //inorder
    //postorder
    //level order all acceptable
    TreeNode *preorder_copy(TreeNode *root)
    {
        TreeNode *t = newTreeNode(root->val);
        t->leftChild = preorder_copy(root->leftChild);
        t->rightChild = preorder_copy(root->rightChild);
        return t;
    }
    ```
* **equal B.T**
    ```cpp
    //preorder
    //inorder
    //postorder
    //level order all acceptable
    bool is_tree_eq(TreeNode *root1, TreeNode *root2)
    {
        bool res = false;
        if(root1 == NULL && root2 == NULL)
            res=true;
        else if(root1->val == root2->val)
        {
            res = true;
            res = is_tree_eq(root1->leftChild);
            res = is_tree_eq(root2->rightChild);
        }
        return res;
            
    }
    ```
* **count B.T nodes**
    ```cpp
    int cnt_tree_nodes(TreeNode *root)
    {
        int nL,nR;
        if(root == NULL)
            return 0;
        else
        {
            nL = cnt_tree_nodes(root->leftChild);
            nR = cnt_tree_nodes(root->rightChild);
            return (nL+nR+1)
        }
    }
    ```
* **B.T height**
    ```cpp
        int height_Tree(TreeNode *root)
        {
            int hL, hR;
            if(root == NULL)
                return 0;
            else
            {
                hL = height_Tree(root->leftChild);
                hR = height_Tree(root->rightChild);
            }
            return max(hL,hR)+1
        }
    ```
* **Swap B.T subtrees**
    ```cpp
    void swap_tree_subtree(TreeNode *root)
    {
        TreeNode *tmp;
        tmp = root->leftChild;
        root->leftChild = root->rightChild;
        root->rightChild = tmp;
        return;
    }
    ```
![](https://hackmd.io/_uploads/H1XXesSeT.png)
## **B.T Application**
### **Expression B.T★**
* **Compiler**
    * Parsing Tree
    * Syntax Tree
* <font color="#3770b4">**Definition**</font>
    * leaf operand
    * non-leaf operator
    * priority = level(node)
    * **parsing**
        * postfix = postorder(T)
        * prefix =  preorder(T)
        * Infix = inorder(T)
:::spoiler **Code**
```cpp
//add opcode in data structure TreeNode
int eval_exp_BT(TreeNode *root)
{
    if(root == NULL)
        return 0;
    if (root->opcode == "n")
        return root->val;
    int resL,resR;
    resL = eval_exp_BT(root->leftChild);
    resR = eval_exp_BT(root->rightChild);
    if(root->opcode == "+")
        return resL+resR;
    else if(root->opcode == "-")
        return resL-resR;
    else if(root->opcode == "*")
        return resL*resR;
    else if(root->opcode == "/")
        return resL/resR;
    else if(root->opcode == "~")'
    {
        if(root->leftChild != NULL)
            return -resL;
        else if(root->rightChild != NULL)
            return -resR;
    }
    return 0;

}
```
:::
![](https://hackmd.io/_uploads/Bk1VvLLlp.png)
[Stack & Queue★★](https://hackmd.io/aNmcv36xRWewhG1lUwTDCw?both)
### **Binary Search Tree BST★★★**
* <font color="#3770b4">**Definition**</font>
    * B.T number of nodes ≥ 0
    * **leftChild < parent < rightChild**
        * **inorder(BST): min->max** (left->parent->right)

    ![](https://i.imgur.com/QdkbgAb.png)
* <font color="#3770b4">**Operation**</font>
    * **Insert**

        ![](https://i.imgur.com/TIVxepC.png)
    * <font color="#eb0029">**Delete**</font>

        There *3* kinds of condition when we deleting the node.
        * *degree(node)=0*
            * leaf, *delete(p_node)*
        * *degree(node)=1*
            * *parent->left/rightChild->(p_node->left/rightChild)*
            * *delete(p_node)*
        * ++*degree(node)=2*++

            There're 2 kinds of way to delete nodes with *degree(node)=2*.

            * *replace(p_node)* with the ++smallest node in right subtree++
            * *replace(p_node)* with the ++largest node in left subtree++

            so the *degree(p_node)=0∨1*, *delete(p_node)* with case 0 or 1

        ![](https://i.imgur.com/hDHltuT.png)

        ![](https://hackmd.io/_uploads/SyvLHvUep.png)
    * **Search in BST**
        ```cpp
        bool bst_search(TreeNode *root, int data)
        {
            TreeNode *curNode = root;
            while(true)
            {
                if(curNode == NULL)
                    return false;
                else
                {
                    if(data == curNode->data)
                    {
                        return true;
                    }
                    else if(data > curNode->data)
                    {
                        curNode = curNode->right;
                    }
                    else if(data < curNode->data)
                    {
                        curNode = curNode->left;
                    }
                }
            }
            return false; 
        }
        ```
	* ==**Search k~th~ small in BST**==
	  ```cpp
	  //add information in TreeNode
	  //th_num=num(left_subTree nodes)+1
	  TreeNode* bst_search_kth(TreeNode *root, int k)
	  {
		  if(root != NULL)
		  {
			  if(k == root->th_num)
				  return root;
			  else if (k < root->th_num)
				  bst_search_kth(root->leftChild, k);
			  else if (k > root->th_num)
				  bst_search_kth(root->rightChild, k-root->th_num);
		  }
	  }
	  ```
	  ![](https://hackmd.io/_uploads/r1GExWQWp.png)
	  :::success
	  **root 為第幾小的數**
	  :::
	* **Example**
		![S__34086914.jpg](https://hackmd.io/_uploads/HkqNhcU7a.jpg)
    * **Complexity**
        * worst case
            * ==*skewed BST O(n)*==
        * best case
            * f*ull/completed BST O(log~2~n)*
            * *smallest height(T)=⌈log2(n+1)⌉*

    ![](https://hackmd.io/_uploads/SkRDltIe6.png)

    :::success
    successful search: *num_compare(node) = level(node)*

    failed search: *num_compare(node) = level(insert(node))-1*
    :::
    ![](https://hackmd.io/_uploads/HJqyKt8ea.png)

    ![](https://hackmd.io/_uploads/HkELztUla.png)

    :::info
    *S = ar^0^+(a+d)r^1^+(a+2d)r^2^...+(a+(n-1)d)r^n-1^*

    *rS =ar^1^+(a+d)r^2^+(a+2d)r^3^...+(a+(n-2)d)r^n-1^+(a+(n-1)d)r^n^*

    *(1-r)S = ar^0^+d(r^1^+r^2^+...+r^n-1^)-(a+(n-1)d)r^n^*
    :::
    ![](https://hackmd.io/_uploads/BkdbsF8x6.png)

    :::info
    when you get BST nodes, you get the *inorder*
    :::
    ![](https://hackmd.io/_uploads/S1Tw2tIxa.png)

    :::info
    *max(left_subtree)<parent<min(right_subtree)*
    :::
    :::spoiler **Code**
    ```c
    #include<bits/stdc++.h>
    using namespace std;
    //struct of tree
    typedef struct TreeNode
    {
        int data;
        TreeNode *left;
        TreeNode *right;
    }TreeNode;

    TreeNode *bst(TreeNode **root);
    bool bst_insert(TreeNode **root, int data);
    bool bst_delete(TreeNode **root, int data);
    bool bst_search(TreeNode *root, int data);
    void bst_print(TreeNode *root);
    void prefix(TreeNode *root)
    {
        if(root!=NULL)
        {
            cout << root->data << " ";
            prefix(root->left);
            prefix(root->right);
        }
        return;
    }
    void infix(TreeNode *root)
    {
        if(root!=NULL)
        {
            infix(root->left);
            cout << root->data << " ";
            infix(root->right);
        }
        return;
    }
    void postfix(TreeNode *root)
    {
        if(root!=NULL)
        {
            postfix(root->left);
            postfix(root->right);
            cout << root -> data << " ";
        }
        return;
    }
    void level(TreeNode *root)
    {
        //bfs
        queue<TreeNode*> q;
        if(root == NULL)
        {
            return;
        }
        q.push(root);
        while(!q.empty())
        {
            TreeNode *curNode = q.front();
            cout << curNode->data << " ";
            if(curNode->left!=NULL)
            { 
                q.push(curNode->left);
            }
            if(curNode->right!=NULL)
            {
                q.push(curNode->right);
            }
            q.pop();
        }
        return;
    }
    bool bst_insert(TreeNode **root, int data)
    {
        //create a new node
        //give the the new TreeNode a new memory location
        TreeNode *newNode = (TreeNode*) malloc(sizeof(TreeNode));

        newNode -> data = data;
        newNode -> left = NULL;
        newNode -> right = NULL;

        //if root is NULL, create a new root
        if(*root==NULL)
        {
            *root = newNode;
            return true;
        }
        else
        {
            TreeNode *curNode = *root;
            while(true)
            {
                if(data == curNode->data)
                    return false;
                //insert in exist bst
                else if(data > curNode->data)
                {
                    //create a treeNode
                    if(curNode->right == NULL)
                    {
                        curNode->right = newNode;
                        return true;
                    }
                    else
                        curNode = curNode->right;
                }
                else if(data < curNode->data)
                {
                    //create a treeNode
                    if(curNode->left == NULL)
                    {                        
                        curNode->left = newNode;
                        return true;
                    }
                    else
                        curNode = curNode->left;
                }

            }
        }
        return false;
    }
    /*
    (1) If the deleted node is a leaf, then delete directly.
    (2) If the deleted node has a child, then replace the deleted node with its child.
    (3) If the deleted node has left and right sub-tree, then replace the deleted node 
        with the smallest node of the right sub-tree.
    */
    bool bst_delete(TreeNode **root, int data)
    {
        TreeNode *curNode = *root;
        TreeNode *preNode = *root;
        if(*root == NULL)
            return false;
        while(true)
        {
            //cannot find TreeNode
            if(curNode == NULL)
                return false;
            //cout << curNode->data << " ";
            //find TreeNode
            if(data == curNode->data)
            {
                //(1)
                if(curNode->left == NULL && curNode->right==NULL)
                {
                    if(curNode->data < preNode->data)
                        preNode->left = NULL;
                    if(curNode->data > preNode->data)
                        preNode->right = NULL;
                    return true;
                }
                //(2)
                if(curNode->left == NULL || curNode->right == NULL)
                {
                    //have left child but no right child
                    if(curNode->left != NULL && curNode->right == NULL)
                    {
                        curNode->data = curNode->left->data;
                        curNode->left = NULL;
                        return true;
                    }
                    //have right child but no left child
                    if(curNode->left == NULL && curNode->right != NULL)
                    {
                        curNode->data = curNode->right->data;
                        curNode->right = NULL;
                        return true;
                    }
                }
                //(3)
                if(curNode->left!=NULL && curNode->right!=NULL)
                {
                    TreeNode* replacedNode = curNode->right;
                    TreeNode* replacedPreNode = curNode->right;
                    //find the smallest TreeNode in right sub-tree
                    //which mean the left-most TreeNode
                    while(replacedNode->left!=NULL)
                    {
                        replacedPreNode = replacedNode;
                        replacedNode = replacedNode->left;
                    }
                    if(replacedNode == replacedPreNode)
                    {
                        curNode->data = replacedNode->data;
                        curNode->right = NULL;
                        return true;
                    }
                    curNode->data = replacedNode->data;
                    replacedPreNode->left = NULL;
                    //replaceNode has right child
                    if(replacedNode->right != NULL)
                    {
                        replacedPreNode->left = replacedNode->right;
                    }
                    return true;
                }
            }
            //Traversal
            else if(data < curNode->data)
            {
                preNode = curNode;
                curNode = curNode->left;
            }
            else if(data > curNode->data)
            {            
                preNode = curNode;
                curNode = curNode->right;
            }
        }
        return false;
    }
    bool bst_search(TreeNode *root, int data)
    {
        TreeNode *curNode = root;
        while(true)
        {
            if(curNode == NULL)
                return false;
            else
            {
                if(data == curNode->data)
                {
                    return true;
                }
                else if(data > curNode->data)
                {
                    curNode = curNode->right;
                }
                else if(data < curNode->data)
                {
                    curNode = curNode->left;
                }
            }
        }
        return false; 
    }
    void bst_print(TreeNode *root)
    {
        cout << "The tree in prefix order: ";
        prefix(root);
        cout << endl;
        cout << "The tree in infix order: ";
        infix(root);
        cout << endl;
        cout << "The tree in postfix order: ";
        postfix(root);
        cout << endl;
        cout << "The tree in level order: ";
        level(root); 
        cout << endl;
        return;
    }
    int main()
    {
        TreeNode *bst_root = NULL;
        bst(&bst_root);
    }
    ```
    :::
### **Calculation★**
* **Construct different B.T**
	\begin{aligned}
	&num(node) = n \\
	&num(BT) = \frac{C\binom{2n}{n}}{(n+1)} \\
	\end{aligned}
    ![](https://hackmd.io/_uploads/S1IgQyuxT.png)
    ![](https://hackmd.io/_uploads/H1S-X1_ga.png)
    ![](https://hackmd.io/_uploads/rknRQk_xp.png)
    ![](https://hackmd.io/_uploads/ryPMVydxp.png)
### **Heap★★★**
* <font color="#3770b4">**Definition**</font>
    
    Heap is a particular ++complete tree (suit to array)++ with two kinds of priority
    * **MaxHeap:** *parent ≥ children*
    * **MinHeap:** *parent ≤ children*
    
    *max/min(Heap) = root->val* ++(priority queue)++
    
    ![](https://hackmd.io/_uploads/Bkrw85Uep.png)
* **Operation** (MaxHeap)
    * **Insert**
        * place *node* at *array[end+1]*
        * compare to it's *parent*
            * *parent < node*
            	* swap and continue
            * *parent > node*
            	* stop
    
    ![](https://hackmd.io/_uploads/r18QYc8l6.png)
    * **Delete**
        * replace *node* by *array[end]*
        * compare to it's *max(childs)*
            * *node < max(childs)*
            	* swap and continue
            * *node->val > max(childs)*
            	* stop
            * *node->childs== NULL*
            	* stop
    
    ![](https://hackmd.io/_uploads/BJOe1sUxT.png)
    * **Build**
        * **Topdown**
            * insert(all_nodes)
            * **Complexity**
                * *O(nlogn)≈log1+log2+..logn=log(n!)*
        
        ![](https://hackmd.io/_uploads/BkVyfsLxa.png)
        * **Bottom-up** (Faster)
            * Build a *complete tree* by input data (top->bottom, left->right)
              ```cpp
              vector<int> heap(heap_size+1,INT_MAX);
              for(int i=1; i<=heap_size; i++)
              cin >> heap[i];
            * ==Compare every *internal nodes* from last to first== 
                ```cpp

                void maxHeapify(vector<int> &heap, int rootIDX)
                {
                    int leftChildIDX = 2 *rootIDX;
                    int rightChildIDX = 2*rootIDX + 1;
                    int largestIDX;    //record index of largest({root, leftChild, rightChild})

                    if(leftChildIDX < heap.size() && heap[leftChildIDX] > heap[rootIDX])
                        largestIDX = leftChildIDX;
                    else
                        largestIDX = rootIDX;

                    if(rightChildIDX < heap.size() && heap[rightChildIDX] > heap[largestIDX])
                        largestIDX = rightChildIDX;

                    if(largestIDX != rootIDX)
                    {
                        swap(heap[largestIDX], heap[rootIDX]);
                        maxHeapify(heap, largestIDX);   //maxheapify the subtree of swapped nodes
                    }
                }
                ```
              
              ```cpp
                void buildMaxHeap(vector<int> &heap)
                {
                    //[n/2] nodes has children
                    //buildMaxHeap from bottom to top (from [n/2] to 1)
                    for(int i=heap.size()/2; i>=1; i--)
                        maxHeapify(heap, i);
                }
              ```

            ![](https://hackmd.io/_uploads/B1nL4i8ga.png)

            ![](https://hackmd.io/_uploads/H1vAXj8lT.png)
            
            * **Complexity**
                ![](https://hackmd.io/_uploads/H1H_5aUxT.png)
                * *h=⌈log~2~(n+1)⌉*
                * *internal node in level i* needs *h-i* comparsion
                * There are *2^i-1^ nodes in level i*
                * Total cost: *from 1 to h Σ(h-i)\*2^i-1^*
                
                :::info
                *(1-r)S = ar^0^+d(r^1^+r^2^+...+r^n-1^)-(a+(n-1)d)r^n^*
                
                *S = 2^h^-2-h+1*
                
                *h=⌈log~2~(n+1)⌉≈⌈log~2~n⌉*
                
                *2^logn^-logn-1=n-logn-1*
                ::: 
                * O(n)
                
               
    :::spoiler **Code**
    ```c
    #include<bits/stdc++.h>

    using namespace std;

    void insertHeap(vector<int> &heap, int val);
    void deleteHeap(vector<int> &heap, int val);
    void maxHeapify(vector<int> &heap, int rootIDX);
    void buildMaxHeap(vector<int> &heap);

    void insertHeap(vector<int> &heap, int val)
    {

        //root == NULL
        if(heap[1]==INT_MAX)
        {
            heap[1] = val;
            return;
        }
        heap.push_back(val);

        for(int i=heap.size()-1; heap[i]>heap[i/2]; i=i/2)
            swap(heap[i], heap[i/2]);
        return;

        //buildMaxHeap(heap);
    }
    void deleteHeap(vector<int> &heap, int val)
    {
        vector<int>::iterator it;
        it = find(heap.begin(), heap.end(), val);
        if(it == heap.end())
            return;
        int deleteIDX = distance(heap.begin(), it);
        swap(heap[deleteIDX], heap[heap.size()-1]);
        heap.pop_back();
        buildMaxHeap(heap);
    }
    void maxHeapify(vector<int> &heap, int rootIDX)
    {
        int leftChildIDX = 2 *rootIDX;
        int rightChildIDX = 2*rootIDX + 1;
        int largestIDX;    //record index of largest({root, leftChild, rightChild})

        if(leftChildIDX < heap.size() && heap[leftChildIDX] > heap[rootIDX])
            largestIDX = leftChildIDX;
        else
            largestIDX = rootIDX;

        if(rightChildIDX < heap.size() && heap[rightChildIDX] > heap[largestIDX])
            largestIDX = rightChildIDX;

        if(largestIDX != rootIDX)
        {
            swap(heap[largestIDX], heap[rootIDX]);
            maxHeapify(heap, largestIDX);   //maxheapify the subtree of swapped nodes
        }
    }
    //bottom-up
    void buildMaxHeap(vector<int> &heap)
    {
        //[n/2] nodes has children
        //buildMaxHeap from bottom to top (from [n/2] to 1)
        for(int i=heap.size()/2; i>=1; i--)
            maxHeapify(heap, i);
    }
    void printHeap(vector<int> heap)
    {
        for(int i=1;i<heap.size();i++)
            cout << heap[i] << " ";
    }
    int main()
    {
        int heap_size = -1;
        cin >> heap_size;
        //heap[0] need to be empty
        vector<int> heap(heap_size+1,INT_MAX);
        for(int i=1; i<=heap_size; i++)
            cin >> heap[i];
        buildMaxHeap(heap);
        //insertHeap(heap, val);
        //deleteHeap(heap, val);
        printHeap(heap);
    }
    ```
    :::
* **Complexity**
    | Op      | Time      |
    | ------- | --------- |
    | Insert  | *O(logn)* |
    | Delete  | *O(logn)* |
    | Max/Min | *O(1)*    |
    | Search  | ==*O(n)*==|
    | Build   | ==*O(n)*==|
# <font color="#365c0c">**Tread Binary Tree**</font>
There will *n+1* links wasted in linked B.T

Take the most of these links
* <font color="#3770b4">**Definition**</font>
    
    The node *ptr* point to depends on *++inorder++*
    * **Head:** A no data node
        * *head->leftchild = root*
        * *head->rightchild = head*
    * **Predecessor:** *node->leftChild* links to previous node in *++inorder++*
        * The first *node->leftChild = head*
    * **Successor:** *node->rightChild* links to next node in *++inorder++*
        * The last *node->rightChild = head* 
    
    :::spoiler **Code**
    ```c
    //add thread_code in data structure TreeNode
    //default is_left_thread = false;
    //default is_right_thread = true;
    //The first node->leftChild = head
    //The last node->rightChild = head
    Treenode* ptr
    if(ptr->leftChild == NULL)
    {
        ptr->is_left_thread = true;
        ptr->leftChild = inorder.predecessor();
    }
    if(ptr->rightChild == NULL)
    {
        ptr->is_right_thread = true;
        ptr->rightChild = inorder.successor();
    }
    
    ```
    :::
    
    If a binary tree inorder is `D B E G A C F`,
    the thread binary tree would be
   ![](https://hackmd.io/_uploads/S1iyayPep.png)


    Can linearly traversal binary tree, which is faster than recursively traversal.
    However they're both *O(n)*.
* **Operation**
    * **Find predecessor**
        * Recurs find the ++left most in right subtree++
        ![](https://i.imgur.com/60l3Rq8.png)
        ```c
        TreeNode *find_predecessor(TreeNode *curNode)
        {
            if(curNode == NULL)
                return NULL;
            //leaf
            else if(curNode->is_left_thread == true &&
                    curNode->is_right_thread == true)
                return curNode->leftChild;
            else if(curNode->rightChild)
               return lefttMost(curNode->rightChild);
            return NULL;
        }
        ```
    * **Find successor**
        * Recurs find the ++right most in left subtree++

        ![](https://i.imgur.com/EZIjcIw.png)
        
        ```c
        TreeNode *find_successor(TreeNode *curNode)
        {
            if(curNode == NULL)
                return NULL;
            //leaf
            if(curNode->is_left_thread == true &&
               curNode->is_right_thread == true)
                return curNode->rightChild;
            if(curNode->leftChild)
               return rightMost(curNode->leftChild);  
            return NULL;
        }
        ```

    * **Insert**
        
        There's *2* condition
        * *node* become another *node's leftChild*
        * *node* become another *node's rightChild*
            * *parent->is_right_thread == true*
              
              ![](https://hackmd.io/_uploads/BJVc4gDl6.png)
            * *parent->is_right_thread == false*

              ![](https://hackmd.io/_uploads/rkf6EeDx6.png)
          :::spoiler **Code**
          ```c
          void insert_thread_BT(TreeNode* root, int val,int p_val, string direction)
          {
              TreeNode *newNode = (TreeNode*) malloc(sizeof(TreeNode));
              new_node->val = val;
              TreeNode* p_node = search(root, p_val);
              if(p_node == NULL)
                  return;
              if(direction == "left")
              {
                  if(p_node->is_left_thread == true)
                  {
                      //1
                      newNode->rightChild = p_node;
                      newNode->is_right_thread = true;
                      //2
                      newNode->leftChild = p_node->leftChild;
                      newNode->is_left_thread = true;
                      //3
                      p_node->leftChild = newNode;
                      targer_node->is_left_thread = false;
                  }
                  else if (p_node->is_left_thread == false)
                  {
                      //1
                      newNode->rightChild = p_node;
                      newNode->is_right_thread = true;
                      //2
                      newNode->leftChild = p_node->leftChild;
                      newNode->is_left_thread = false;
                      p_node->leftChild = newNode;
                      //3
                      targer_node->is_left_thread = false;
                      //4
                      tmp = find_perdecessor(p_node);
                      tmp->right_child = p_node;

                  }
              }
              else if(direction == "right")
              {
                  if(p_node->is_right_thread == true)
                  {
                      //1
                      newNode->leftChild = p_node;
                      newNode->is_left_thread = true;
                      //2
                      newNode->rightChild = p_node->rightChild;
                      newNode->is_right_thread = true;
                      //3
                      p_node->rightChild = newNode;
                      targer_node->is_right_thread = false;
                  }
                  else if (p_node->is_right_thread == false)
                  {
                      //1
                      newNode->leftChild = p_node;
                      newNode->is_left_thread = true;
                      //2
                      newNode->rightChild = p_node->rightChild;
                      newNode->is_right_thread = false;
                      //3
                      p_node->rightChild = newNode;
                      targer_node->is_right_thread = false;
                      //4
                      tmp = find_successor(p_node);
                      tmp->left_child = p_node;
                  }
              }
          }
          ```
          :::
    * **Delete**
        * not-defined
    :::spoiler **Code**
    ```c
    typedef struct TreeNode
    {
        int val;
        //0:left subTree, 1:predecessor
        int leftType;
        //0:right subTree, 1:successor
        int rightType;
        TreeNode* leftChild;
        TreeNode* rightChild;
    }TreeNode;

    TreeNode *threadedNode(TreeNode* prev,TreeNode *curNode)
    {
        if(curNode == NULL)
            return NULL;
        threadedNode(prev, curNode->leftChild);
        //predecessor
        if(curNode->leftChild == NULL)
        {
            curNode->leftChild = prev;
            curNode->leftType = 1;
        }
        //successor
        if(prev != NULL && prev->rightChild == NULL)
        {
            pre->rightChild = curNode;
            pre->rightTypr = 1;
        }
        prev = curNode;
        treadedNode(prev, curNode->rightChild);
    }
    void threadList(TreeNode *curNode)
    {
        while(curNode != NULL)
        {
            //find the first element of inorder
            while(curNode->leftType == 0)
            {
                curNode = curNode->leftChild;
            }
            output(curNode);
            while(curNode->rightType == 1)
            {
                curNode = curNode->rightChild;
                output(curNode);
            }
            curNode = curNode->rightChild;
        }
    }
    int main()
    {
        TreeNode *prev = NULL;
        TreeNode *root = creatTree();
        threadNode(prev, root);
        threadList(root);
    }
    ```
    :::
# <font color="#365c0c">**Transform to B.T**</font>
## **N-ary Tree to B.T**
* <font color="#3770b4">**Definition**</font>
    * the first child (from left to right)
        * *parent->leftChild = leftMost(parent's children)*
    * other children
        * *node->rightChild = node's right_sibling*
        * *delete the link from parent to child*
        * (rotate clockwise 45^o^)

![](https://hackmd.io/_uploads/r1IJu0DeT.png)

![](https://hackmd.io/_uploads/SkjIo0vga.png)
## **Forest to B.T**
* <font color="#3770b4">**Definition**</font>
    * every tree in forest *TtoBT(T)*
    * *root_1->rightChild = root_2->rightChild (from left to right)*

![](https://hackmd.io/_uploads/SJuRaRvlT.png)

![](https://hackmd.io/_uploads/rkg-AADxT.png)

# **Course Connection**
* [Disjoint Set](https://hackmd.io/vC9SXISoRSSKptuJMfcVrw)
* [Advance Tree](https://hackmd.io/d8ukUmPHS3iB4WGEimz5kw)